A new class of non-Shannon-type inequalities for entropies. - Konstantin Makarychev; Yury Makarychev; Andrei E. Romashchenko; Nikolai K. Vereshchagin (Commun. Inf. Syst., 2002)

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. - Amit Agarwal; Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2005)

Quadratic forms on graphs. - Noga Alon; Konstantin Makarychev; Yury Makarychev; Assaf Naor (STOC, 2005)

Conditionally independent random variables - Konstantin Makarychev; Yury Makarychev (CoRR, 2005)

How to Play Unique Games Using Embeddings. - Eden Chlamtac; Konstantin Makarychev; Yury Makarychev (FOCS, 2006)

Directed metrics and directed graph partitioning problems. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SODA, 2006)

Near-optimal algorithms for unique games. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2006)

Approximation Algorithm for the Max k-CSP Problem. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2006)

Note on MAX 2SAT. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2006)

A divide and conquer algorithm for d-dimensional arrangement. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SODA, 2007)

On the Advantage over Random for Maximum Acyclic Subgraph. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2007)

Improving Memory Access Locality for Large-Scale Graph Analysis Applications. - Guojing Cong; Konstantin Makarychev (PDCCS, 2009)

On Hardness of Pricing Items for Single-Minded Bidders. - Rohit Khandekar; Tracy Kimbrel; Konstantin Makarychev; Maxim Sviridenko (APPROX-RANDOM, 2009)

Indexing genomic sequences on the IBM Blue Gene. - Amol Ghoting; Konstantin Makarychev (SC, 2009)

Serial and parallel methods for i/o efficient suffix tree construction. - Amol Ghoting; Konstantin Makarychev (SIGMOD Conference, 2009)

Integrality gaps for Sherali-Adams relaxations. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (STOC, 2009)

How to Play Unique Games on Expanders. - Konstantin Makarychev; Yury Makarychev (Electron. Colloquium Comput. Complex., 2009)

Near-optimal algorithms for maximum constraint satisfaction problems. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (ACM Trans. Algorithms, 2009)

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. - Konstantin Makarychev; Yury Makarychev (FOCS, 2010)

Improved Approximation for the Directed Spanner Problem - Arnab Bhattacharyya 001; Konstantin Makarychev (CoRR, 2010)

Local Global Tradeoffs in Metric Embeddings. - Moses Charikar; Konstantin Makarychev; Yury Makarychev (SIAM J. Comput., 2010)

I/O efficient algorithms for serial and parallel suffix tree construction. - Amol Ghoting; Konstantin Makarychev (ACM Trans. Database Syst., 2010)

Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers. - Philip C. Church; Andrzej Goscinski; Kathryn E. Holt; Michael Inouye; Amol Ghoting; Konstantin Makarychev; Matthias Reumann (EMBC, 2011)

The Grothendieck Constant is Strictly Smaller than Krivine's Bound. - Mark Braverman; Konstantin Makarychev; Yury Makarychev; Assaf Naor (FOCS, 2011)

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. - Alexandra Kolla; Konstantin Makarychev; Yury Makarychev (FOCS, 2011)

Improved Approximation for the Directed Spanner Problem. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (ICALP (1), 2011)

Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. - Konstantin Makarychev; Alantha Newman (ICS, 2011)

Optimizing Large-Scale Graph Analysis on a Multi-threaded, Multi-core Platform. - Guojing Cong; Konstantin Makarychev (IPDPS, 2011)

On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. - Howard J. Karloff; Flip Korn; Konstantin Makarychev; Yuval Rabani (STACS, 2011)

How to Play Unique Games against a Semi-Random Adversary - Alexandra Kolla; Konstantin Makarychev; Yury Makarychev (CoRR, 2011)

Suffix Trees. - Amol Ghoting; Konstantin Makarychev (Encyclopedia of Parallel Computing, 2011)

Approximation Algorithm for Non-boolean MAX k-CSP. - Konstantin Makarychev; Yury Makarychev (APPROX-RANDOM, 2012)

Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms. - Guojing Cong; Konstantin Makarychev (IPDPS, 2012)

Approximation algorithms for semi-random partitioning problems. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2012)

Approximation Algorithms for Semi-random Graph Partitioning Problems - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2012)

Chain Independence and Common Information. - Konstantin Makarychev; Yury Makarychev (IEEE Trans. Inf. Theory, 2012)

Speed regularization and optimality in word classing. - Geoffrey Zweig; Konstantin Makarychev (ICASSP, 2013)

Sorting noisy data with partial information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (ITCS, 2013)

Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. - Konstantin Makarychev (STACS, 2013)

Approximation Algorithm for Sparsest k-Partitioning. - Anand Louis; Konstantin Makarychev (CoRR, 2013)

Bilu-Linial Stable Instances of Max Cut - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2013)

Approximation algorithms for spanner problems and Directed Steiner Forest. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (Inf. Comput., 2013)

Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms. - Niv Buchbinder; Tracy Kimbrel; Retsef Levi; Konstantin Makarychev; Maxim Sviridenko (Oper. Res., 2013)

Nonuniform Graph Partitioning with Unrelated Weights. - Konstantin Makarychev; Yury Makarychev (ICALP (1), 2014)

Precedence-Constrained Scheduling of Malleable Jobs with Preemption. - Konstantin Makarychev; Debmalya Panigrahi (ICALP (1), 2014)

Approximation Algorithm for Sparsest k-Partitioning. - Anand Louis; Konstantin Makarychev (SODA, 2014)

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (SODA, 2014)

Constant factor approximation for balanced cut in the PIE model. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2014)

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. - Shuchi Chawla 001; Konstantin Makarychev; Tselil Schramm; Grigory Yaroslavtsev (CoRR, 2014)

Online Algorithms for Machine Minimization. - Nikhil R. Devanur; Konstantin Makarychev; Debmalya Panigrahi; Grigory Yaroslavtsev (CoRR, 2014)

Algorithms for Semi-random Correlation Clustering. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2014)

Optimization Problems with Diseconomies of Scale via Decoupling. - Konstantin Makarychev; Maxim Sviridenko (CoRR, 2014)

Min-Max Graph Partitioning and Small Set Expansion. - Nikhil Bansal 001; Uriel Feige; Robert Krauthgamer; Konstantin Makarychev; Viswanath Nagarajan; Joseph Naor; Roy Schwartz 002 (SIAM J. Comput., 2014)

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm. - Konstantin Makarychev; Rajsekar Manokaran; Maxim Sviridenko (ACM Trans. Algorithms, 2014)

Approximation Algorithm for Non-Boolean Max-k-CSP. - Konstantin Makarychev; Yury Makarychev (Theory Comput., 2014)

Correlation Clustering with Noisy Partial Information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2015)

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. - Konstantin Makarychev; Yury Makarychev; Yuan Zhou 007 (FOCS, 2015)

Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. - Virajith Jalaparti; Peter Bodík; Ishai Menache; Sriram Rao; Konstantin Makarychev; Matthew Caesar 001 (SIGCOMM, 2015)

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. - Shuchi Chawla 001; Konstantin Makarychev; Tselil Schramm; Grigory Yaroslavtsev (STOC, 2015)

Satisfiability of Ordering CSPs Above Average. - Konstantin Makarychev; Yury Makarychev; Yuan Zhou 007 (CoRR, 2015)

Concentration inequalities for nonlinear matroid intersection. - Konstantin Makarychev; Warren Schudy; Maxim Sviridenko (Random Struct. Algorithms, 2015)

A Bi-Criteria Approximation Algorithm for k-Means. - Konstantin Makarychev; Yury Makarychev; Maxim Sviridenko; Justin Ward (APPROX-RANDOM, 2016)

Learning Communities in the Presence of Errors. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2016)

Metric Perturbation Resilience. - Konstantin Makarychev; Yury Makarychev (CoRR, 2016)

Approximation Algorithms for CSPs. - Konstantin Makarychev; Yury Makarychev (The Constraint Satisfaction Problem, 2017)

Clustering Billions of Reads for DNA Data Storage. - Cyrus Rashtchian; Konstantin Makarychev; Miklós Z. Rácz; Siena Ang; Djordje Jevdjic; Sergey Yekhanin; Luis Ceze; Karin Strauss (NIPS, 2017)

Algorithms for stable and perturbation-resilient problems. - Haris Angelidakis; Konstantin Makarychev; Yury Makarychev (STOC, 2017)

Maximizing Polynomials Subject to Assignment Constraints. - Konstantin Makarychev; Maxim Sviridenko (ACM Trans. Algorithms, 2017)

Nonlinear dimension reduction via outer Bi-Lipschitz extensions. - Sepideh Mahabadi; Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (STOC, 2018)

Solving Optimization Problems with Diseconomies of Scale via Decoupling. - Konstantin Makarychev; Maxim Sviridenko (J. ACM, 2018)

Correlation clustering with local objectives. - Sanchit Kalhan; Konstantin Makarychev; Timothy Zhou (NeurIPS, 2019)

Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. - Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (STOC, 2019)

Improved algorithms for Correlation Clustering with local objectives. - Sanchit Kalhan; Konstantin Makarychev; Timothy Zhou (CoRR, 2019)

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. - Víctor Dalmau; Marcin Kozik; Andrei A. Krokhin; Konstantin Makarychev; Yury Makarychev; Jakub Oprsal (SIAM J. Comput., 2019)

Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. - Konstantin Makarychev; Yury Makarychev; Ilya P. Razenshteyn (SIAM J. Comput., 2019)

Perturbation Resilience. - Konstantin Makarychev; Yury Makarychev (Beyond the Worst-Case Analysis of Algorithms, 2020)

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. - Vaggos Chatziafratis; Grigory Yaroslavtsev; Euiwoong Lee; Konstantin Makarychev; Sara Ahmadian; Alessandro Epasto; Mohammad Mahdian (AISTATS, 2020)

Correlation Clustering with Asymmetric Classification Errors. - Jafar Jafarov; Sanchit Kalhan; Konstantin Makarychev; Yury Makarychev (ICML, 2020)

Certified Algorithms: Worst-Case Analysis and Beyond. - Konstantin Makarychev; Yury Makarychev (ITCS, 2020)

Improved Guarantees for k-means++ and k-means++ Parallel. - Konstantin Makarychev; Aravind Reddy; Liren Shan (NeurIPS, 2020)

Two-Sided Kirszbraun Theorem. - Arturs Backurs; Sepideh Mahabadi; Konstantin Makarychev; Yury Makarychev (SoCG, 2021)

Local Correlation Clustering with Asymmetric Classification Errors. - Jafar Jafarov; Sanchit Kalhan; Konstantin Makarychev; Yury Makarychev (ICML, 2021)

Near-Optimal Algorithms for Explainable k-Medians and k-Means. - Konstantin Makarychev; Liren Shan (ICML, 2021)

Explainable k-means. Don't be greedy, plant bigger trees! - Konstantin Makarychev; Liren Shan (CoRR, 2021)

Explainable k-means: don't be greedy, plant bigger trees! - Konstantin Makarychev; Liren Shan (STOC, 2022)

Phylogenetic CSPs are Approximation Resistant. - Vaggos Chatziafratis; Konstantin Makarychev (CoRR, 2022)

Batch Optimization for DNA Synthesis. - Konstantin Makarychev; Miklós Z. Rácz; Cyrus Rashtchian; Sergey Yekhanin (IEEE Trans. Inf. Theory, 2022)

Approximation Algorithm for Norm Multiway Cut. - Charlie Carlson; Jafar Jafarov; Konstantin Makarychev; Yury Makarychev; Liren Shan (ESA, 2023)

Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. - Vaggos Chatziafratis; Konstantin Makarychev (FOCS, 2023)

Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! - Konstantin Makarychev; Sayak Chakrabarty (NeurIPS, 2023)

Random Cuts are Optimal for Explainable k-Medians. - Konstantin Makarychev; Liren Shan (NeurIPS, 2023)

Approximation Algorithms for Norm Multiway Cut. - Charlie Carlson; Jafar Jafarov; Konstantin Makarychev; Yury Makarychev; Liren Shan (CoRR, 2023)

Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. - Dmitrii Avdiukhin; Vaggos Chatziafratis; Konstantin Makarychev; Grigory Yaroslavtsev (AAAI, 2024)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. - Mina Dalirrooyfard; Konstantin Makarychev; Slobodan Mitrovic (ICML, 2024)

Higher-Order Cheeger Inequality for Partitioning with Buffers. - Konstantin Makarychev; Yury Makarychev; Liren Shan; Aravindan Vijayaraghavan (SODA, 2024)

Constraint Satisfaction Problems with Advice. - Suprovat Ghoshal; Konstantin Makarychev; Yury Makarychev (SODA, 2025)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions. - Mina Dalirrooyfard; Konstantin Makarychev; Slobodan Mitrovic (CoRR, 2025)