Konstantin Makarychev

Best Publications

• Random access in large-scale DNA data storage

  Lee Organick;Siena Dumas Ang;Yuan Jyue Chen;Randolph Lopez

  753
  Citations

• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

  Amit Agarwal;Moses Charikar;Konstantin Makarychev;Yury Makarychev

  220
  Citations

• Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can

  Virajith Jalaparti;Peter Bodik;Ishai Menache;Sriram Rao

  212
  Citations

• Space-Efficient Identity Based EncryptionWithout Pairings

  D. Boneh;C. Gentry;M. Hamburg

  192
  Citations

• Near-optimal algorithms for unique games

  Moses Charikar;Konstantin Makarychev;Yury Makarychev

  174
  Citations

• A NEW CLASS OF NON-SHANNON-TYPE INEQUALITIES FOR ENTROPIES

  Unknown

  164
  Citations

• Near-optimal algorithms for maximum constraint satisfaction problems

  Moses Charikar;Konstantin Makarychev;Yury Makarychev

  161
  Citations

• DNA assembly for nanopore data storage readout.

  Randolph Lopez;Yuan Jyue Chen;Siena Dumas Ang;Sergey Yekhanin

  147
  Citations

• Min-Max Graph Partitioning and Small Set Expansion

  Nikhil Bansal;Uriel Feige;Robert Krauthgamer;Konstantin Makarychev

  143
  Citations

• Integrality gaps for Sherali-Adams relaxations

  Moses Charikar;Konstantin Makarychev;Yury Makarychev

  140
  Citations

• Quadratic forms on graphs

  Noga Mordechai Alon;Konstantin Makarychev;Yury Makarychev;Assaf Naor

  112
  Citations

• Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering

  Unknown

  99
  Citations

• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

  Shuchi Chawla;Konstantin Makarychev;Tselil Schramm;Grigory Yaroslavtsev

  95
  Citations

• THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND

  Mark Braverman;Konstantin Makarychev;Yury Makarychev;Assaf Naor

  85
  Citations

• How to Play Unique Games Using Embeddings

  Eden Chlamtac;Konstantin Makarychev;Yury Makarychev

  83
  Citations

• Approximation algorithms for semi-random partitioning problems

  Konstantin Makarychev;Yury Makarychev;Aravindan Vijayaraghavan

  70
  Citations

• Metric extension operators, vertex sparsifiers and Lipschitz extendability

  Konstantin Makarychev;Yury Makarychev

  69
  Citations

• Sparse Random Linear Codes are Locally Decodable and Testable

  T. Kaufman;M. Sudan

  65
  Citations

• Bilu-linial stable instances of max cut and minimum multiway cut

  Konstantin Makarychev;Yury Makarychev;Aravindan Vijayaraghavan

  64
  Citations

• Near-optimal algorithms for maximum constraint satisfaction problems

  Moses Charikar;Konstantin Makarychev;Yury Makarychev

  59
  Citations