pith. machine review for the scientific record. sign in

Marek Karpinski

Identifiers

  • name variant Marek Karpinski 0.60 · backfill

Papers (49)

  1. Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields cs.CC · 2017 · author #1
  2. Approximation Complexity of Max-Cut on Power Law Graphs cs.DS · 2016 · author #3
  3. Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications cs.CC · 2015 · author #2
  4. Approximability of TSP on Power Law Graphs cs.DS · 2015 · author #3
  5. Explicit Bounds for Nondeterministically Testable Hypergraph Parameters cs.DS · 2015 · author #1
  6. On the Complexity of Nondeterministically Testable Hypergraph Parameters cs.DS · 2015 · author #1
  7. On the Approximability of Independent Set Problem on Power Law Graphs cs.DS · 2015 · author #2
  8. Polynomial Interpolation and Identity Testing from High Powers over Finite Fields math.NT · 2015 · author #2
  9. A QPTAS for the Base of the Number of Triangulations of a Planar Point Set cs.CG · 2014 · author #1
  10. Complexity of Nondeterministic Graph Parameter Testing cs.DS · 2014 · author #1
  11. Limits of CSP Problems and Efficient Parameter Testing cs.DS · 2014 · author #1
  12. Approximate Counting of Matchings in $(3,3)$-Hypergraphs math.CO · 2014 · author #2
  13. Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks cs.CC · 2013 · author #3
  14. Generalized Wong sequences and their applications to Edmonds' problems cs.CC · 2013 · author #2
  15. Approximation Hardness of Graphic TSP on Cubic Graphs cs.CC · 2013 · author #1
  16. New Inapproximability Bounds for TSP cs.CC · 2013 · author #1
  17. Inapproximability of Dominating Set in Power Law Graphs cs.CC · 2012 · author #3
  18. Optimal Cuts and Partitions in Tree Metrics in Polynomial Time cs.DS · 2012 · author #1
  19. Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations cs.CC · 2012 · author #3
  20. Optimal Cuts and Bisections on the Real Line in Polynomial Time cs.DS · 2012 · author #1
  21. Deterministic Polynomial Factoring and Association Schemes cs.CC · 2012 · author #3
  22. Approximate Counting of Matchings in Sparse Uniform Hypergraphs cs.DS · 2012 · author #1
  23. Approximate Counting of Matchings in Sparse Hypergraphs cs.DS · 2012 · author #1
  24. On Approximation Lower Bounds for TSP with Bounded Metrics cs.CC · 2012 · author #1
  25. Improved Lower Bounds for the Shortest Superstring and Related Problems cs.CC · 2011 · author #1
  26. On the Computational Complexity of Measuring Global Stability of Banking Networks q-fin.RM · 2011 · author #4
  27. Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs cs.DS · 2011 · author #1
  28. Approximating Vertex Cover in Dense Hypergraphs cs.DS · 2010 · author #2
  29. Approximating Subdense Instances of Covering Problems cs.DS · 2010 · author #2
  30. Top-K Color Queries for Document Retrieval cs.DS · 2010 · author #1
  31. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament cs.DS · 2010 · author #1
  32. Range Reporting for Moving Points on a Grid cs.DS · 2010 · author #1
  33. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems cs.DS · 2009 · author #1
  34. Deterministic Polynomial Time Algorithms for Matrix Completion Problems cs.DS · 2009 · author #2
  35. Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications cs.CC · 2009 · author #2
  36. A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two cs.CC · 2008 · author #2
  37. Low-Memory Adaptive Prefix Coding cs.DS · 2008 · author #2
  38. Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems cs.DS · 2008 · author #1
  39. Trading GRH for algebra: algorithms for factoring polynomials and related structures cs.CC · 2008 · author #2
  40. 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two cs.CC · 2008 · author #2
  41. Approximating Transitivity in Directed Networks cs.CC · 2008 · author #3
  42. Space Efficient Multi-Dimensional Range Reporting cs.DS · 2008 · author #1
  43. The Mixing Time of Glauber Dynamics for Colouring Regular Trees cs.CC · 2008 · author #3
  44. Searching for Frequent Colors in Rectangles cs.DS · 2008 · author #1
  45. Schemes for Deterministic Polynomial Factoring cs.CC · 2008 · author #2
  46. Metric Construction, Stopping Times and Path Coupling math.PR · 2005 · author #3
  47. Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs math.PR · 2005 · author #3
  48. On Computational Power of Quantum Branching Programs quant-ph · 2003 · author #3
  49. Quantum finite multitape automata quant-ph · 1999 · author #5

Mentions

  • 0911.2214 #1 · backfill · confidence 0.70 Marek Karpinski
  • 0907.0774 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0904.2310 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0812.2137 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0811.3602 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0811.3244 #1 · backfill · confidence 0.70 Marek Karpinski
  • 0811.3165 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0810.1851 #2 · backfill · confidence 0.70 Marek Karpinski
  • 0809.0188 #3 · backfill · confidence 0.70 Marek Karpinski
  • 0806.4361 #1 · backfill · confidence 0.70 Marek Karpinski
  • 0806.0921 #3 · backfill · confidence 0.70 Marek Karpinski
  • 0805.1348 #1 · backfill · confidence 0.70 Marek Karpinski
  • 0804.1974 #2 · backfill · confidence 0.70 Marek Karpinski

Frequent Coauthors