Konstantin Makarychev

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 46

Top Venues

CoRR

STOC

SODA

NeurIPS

Publications

Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA (2024)
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
Constraint Satisfaction Problems with Advice. CoRR (2024)
Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. AAAI (2024)
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. CoRR (2024)
Vaggos Chatziafratis, Konstantin Makarychev
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. FOCS (2023)
Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR (2023)
Konstantin Makarychev, Sayak Chakrabarty
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! NeurIPS (2023)
Sayak Chakrabarty, Konstantin Makarychev
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! CoRR (2023)
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
Approximation Algorithms for Norm Multiway Cut. CoRR (2023)
Konstantin Makarychev, Liren Shan
Random Cuts are Optimal for Explainable k-Medians. NeurIPS (2023)
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
Approximation Algorithm for Norm Multiway Cut. ESA (2023)
Konstantin Makarychev, Liren Shan
Random Cuts are Optimal for Explainable k-Medians. CoRR (2023)
Konstantin Makarychev, Liren Shan
-means: don't be greedy, plant bigger trees! STOC (2022)
Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
Batch Optimization for DNA Synthesis. IEEE Trans. Inf. Theory 68 (11) (2022)
Vaggos Chatziafratis, Konstantin Makarychev
Phylogenetic CSPs are Approximation Resistant. CoRR (2022)
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
Two-Sided Kirszbraun Theorem. SoCG (2021)
Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
Batch Optimization for DNA Synthesis. ISIT (2021)
Konstantin Makarychev, Liren Shan
Explainable k-means. Don't be greedy, plant bigger trees! CoRR (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Local Correlation Clustering with Asymmetric Classification Errors. ICML (2021)
Konstantin Makarychev, Liren Shan
Near-Optimal Algorithms for Explainable k-Medians and k-Means. ICML (2021)
Konstantin Makarychev, Liren Shan
Near-optimal Algorithms for Explainable k-Medians and k-Means. CoRR (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Local Correlation Clustering with Asymmetric Classification Errors. CoRR (2021)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Correlation Clustering with Asymmetric Classification Errors. CoRR (2021)
Konstantin Makarychev, Aravind Reddy, Liren Shan
Improved Guarantees for k-means++ and k-means++ Parallel. NeurIPS (2020)
Konstantin Makarychev, Yury Makarychev
Certified Algorithms: Worst-Case Analysis and Beyond. ITCS (2020)
Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. AISTATS (2020)
Konstantin Makarychev, Aravind Reddy, Liren Shan
Improved Guarantees for k-means++ and k-means++ Parallel. CoRR (2020)
Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
Batch Optimization for DNA Synthesis. CoRR (2020)
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
Correlation Clustering with Asymmetric Classification Errors. ICML (2020)
Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
Improved algorithms for Correlation Clustering with local objectives. CoRR (2019)
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. CoRR (2019)
Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
Correlation clustering with local objectives. NeurIPS (2019)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. 48 (6) (2019)
Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
-medians clustering. STOC (2019)
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions. CoRR (2018)
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Nonlinear dimension reduction via outer Bi-Lipschitz extensions. STOC (2018)
Konstantin Makarychev, Maxim Sviridenko
Solving Optimization Problems with Diseconomies of Scale via Decoupling. J. ACM 65 (6) (2018)
Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering. CoRR (2018)
Haris Angelidakis, Konstantin Makarychev, Yury Makarychev
Algorithms for stable and perturbation-resilient problems. STOC (2017)
Cyrus Rashtchian, Konstantin Makarychev, Miklós Z. Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, Karin Strauss
Clustering Billions of Reads for DNA Data Storage. NIPS (2017)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. SODA (2017)
Konstantin Makarychev, Maxim Sviridenko
Maximizing Polynomials Subject to Assignment Constraints. ACM Trans. Algorithms 13 (4) (2017)
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
A Bi-Criteria Approximation Algorithm for k-Means. APPROX-RANDOM (2016)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Learning Communities in the Presence of Errors. COLT (2016)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR (2016)
Konstantin Makarychev, Yury Makarychev
Metric Perturbation Resilience. CoRR (2016)
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. FOCS (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Correlation Clustering with Noisy Partial Information. COLT (2015)
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. STOC (2015)
Virajith Jalaparti, Peter Bodík, Ishai Menache, Sriram Rao, Konstantin Makarychev, Matthew Caesar
Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. SIGCOMM (2015)
Peter Bodík, Virajith Jalaparti, Sriram Rao, Matthew Caesar, Ishai Menache, Konstantin Makarychev
Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. Computer Communication Review (2015)
Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
Concentration inequalities for nonlinear matroid intersection. Random Struct. Algorithms 46 (3) (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Learning Communities in the Presence of Errors. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Satisfiability of Ordering CSPs Above Average. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
A bi-criteria approximation algorithm for k Means. CoRR (2015)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Algorithms for Semi-random Correlation Clustering. CoRR (2014)
Konstantin Makarychev, Maxim Sviridenko
Solving Optimization Problems with Diseconomies of Scale via Decoupling. FOCS (2014)
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm. CoRR (2014)
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm. ACM Trans. Algorithms 10 (4) (2014)
Konstantin Makarychev, Debmalya Panigrahi
Precedence-Constrained Scheduling of Malleable Jobs with Preemption. ICALP (1) (2014)
Konstantin Makarychev, Yury Makarychev
-CSP. Theory Comput. 10 (2014)
Konstantin Makarychev, Maxim Sviridenko
Optimization Problems with Diseconomies of Scale via Decoupling. CoRR (2014)
Konstantin Makarychev, Yury Makarychev
Nonuniform Graph Partitioning with Unrelated Weights. ICALP (1) (2014)
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. CoRR (2014)
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. 43 (2) (2014)
Konstantin Makarychev, Debmalya Panigrahi
Precedence-constrained Scheduling of Malleable Jobs with Preemption. CoRR (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Constant Factor Approximation for Balanced Cut in the PIE model. CoRR (2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Constant factor approximation for balanced cut in the PIE model. STOC (2014)
Konstantin Makarychev, Yury Makarychev
Nonuniform Graph Partitioning with Unrelated Weights. CoRR (2014)
Nikhil R. Devanur, Konstantin Makarychev, Debmalya Panigrahi, Grigory Yaroslavtsev
Online Algorithms for Machine Minimization. CoRR (2014)
Anand Louis, Konstantin Makarychev
-Partitioning. SODA (2014)
Anand Louis, Konstantin Makarychev
Approximation Algorithm for Sparsest k-Partitioning. CoRR (2013)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. 222 (2013)
Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko
Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms. Oper. Res. 61 (4) (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Sorting noisy data with partial information. ITCS (2013)
Geoffrey Zweig, Konstantin Makarychev
Speed regularization and optimality in word classing. ICASSP (2013)
Konstantin Makarychev
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. STACS (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Bilu-Linial Stable Instances of Max Cut CoRR (2013)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Approximation algorithms for semi-random partitioning problems. STOC (2012)
Konstantin Makarychev, Yury Makarychev
Approximation Algorithm for Non-boolean MAX k-CSP. APPROX-RANDOM (2012)
Konstantin Makarychev, Yury Makarychev
Chain Independence and Common Information. IEEE Trans. Inf. Theory 58 (8) (2012)
Guojing Cong, Konstantin Makarychev
Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms. IPDPS (2012)
Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
Concentration inequalities for nonlinear matroid intersection. SODA (2012)
Konstantin Makarychev
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs CoRR (2012)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Approximation Algorithms for Semi-random Graph Partitioning Problems CoRR (2012)
Konstantin Makarychev, Yury Makarychev
Approximation Algorithm for Non-Boolean MAX k-CSP CoRR (2012)
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
Min-Max Graph Partitioning and Small Set Expansion CoRR (2011)
Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
Min-max Graph Partitioning and Small Set Expansion. FOCS (2011)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck constant is strictly smaller than Krivine's bound. CoRR (2011)
Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data CoRR (2011)
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. FOCS (2011)
Philip C. Church, Andrzej Goscinski, Kathryn E. Holt, Michael Inouye, Amol Ghoting, Konstantin Makarychev, Matthias Reumann
Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers. EMBC (2011)
Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
Improved Approximation for the Directed Spanner Problem. ICALP (1) (2011)
Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
How to Play Unique Games against a Semi-Random Adversary CoRR (2011)
Guojing Cong, Konstantin Makarychev
Optimizing Large-Scale Graph Analysis on a Multi-threaded, Multi-core Platform. IPDPS (2011)
Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. STACS (2011)
Konstantin Makarychev, Alantha Newman
Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. ICS (2011)
Konstantin Makarychev, Maxim Sviridenko
Maximizing Polynomials Subject to Assignment Constraints. ICALP (1) (2011)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS (2011)

Konstantin Makarychev.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Konstantin Makarychev