Konstantin Makarychev

CoRR, 2024

Higher-Order Cheeger Inequality for Partitioning with Buffers.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models.

[BibT_eX]

[DOI]

Mina Dalirrooyfard

Slobodan Mitrovic

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Approximation Scheme for Weighted Metric Clustering via Sherali-Adams.

[BibT_eX]

[DOI]

Dmitrii Avdiukhin

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Approximation Algorithms for Norm Multiway Cut.

[BibT_eX]

[DOI]

Charlie Carlson

CoRR, 2023

Random Cuts are Optimal for Explainable k-Medians.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!

[BibT_eX]

[DOI]

Sayak Chakrabarty

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Approximation Algorithm for Norm Multiway Cut.

[BibT_eX]

[DOI]

Charlie Carlson

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Batch Optimization for DNA Synthesis.

[BibT_eX]

[DOI]

Miklós Z. Rácz

Cyrus Rashtchian

Sergey Yekhanin

IEEE Trans. Inf. Theory, 2022

Phylogenetic CSPs are Approximation Resistant.

[BibT_eX]

[DOI]

CoRR, 2022

Explainable k-means: don't be greedy, plant bigger trees!

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Explainable k-means. Don't be greedy, plant bigger trees!

[BibT_eX]

[DOI]

CoRR, 2021

Near-Optimal Algorithms for Explainable k-Medians and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Local Correlation Clustering with Asymmetric Classification Errors.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Two-Sided Kirszbraun Theorem.

[BibT_eX]

[DOI]

Arturs Backurs

Sepideh Mahabadi

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Improved Guarantees for k-means++ and k-means++ Parallel.

[BibT_eX]

[DOI]

Aravind Reddy

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Certified Algorithms: Worst-Case Analysis and Beyond.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Correlation Clustering with Asymmetric Classification Errors.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection.

[BibT_eX]

[DOI]

Euiwoong Lee

Sara Ahmadian

Alessandro Epasto

Mohammad Mahdian

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Perturbation Resilience.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.

[BibT_eX]

[DOI]

Víctor Dalmau

Marcin Kozik

Andrei A. Krokhin

Jakub Oprsal

SIAM J. Comput., 2019

Improved algorithms for Correlation Clustering with local objectives.

[BibT_eX]

[DOI]

Timothy Zhou

CoRR, 2019

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

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Correlation clustering with local objectives.

[BibT_eX]

[DOI]

Timothy Zhou

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Solving Optimization Problems with Diseconomies of Scale via Decoupling.

[BibT_eX]

[DOI]

J. ACM, 2018

Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

CoRR, 2018

Nonlinear dimension reduction via outer Bi-Lipschitz extensions.

[BibT_eX]

[DOI]

Sepideh Mahabadi

Ilya P. Razenshteyn

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Maximizing Polynomials Subject to Assignment Constraints.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Algorithms for stable and perturbation-resilient problems.

[BibT_eX]

[DOI]

Haris Angelidakis

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Clustering Billions of Reads for DNA Data Storage.

[BibT_eX]

[DOI]

Cyrus Rashtchian

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximation Algorithms for CSPs.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Metric Perturbation Resilience.

[BibT_eX]

[DOI]

CoRR, 2016

Learning Communities in the Presence of Errors.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

A Bi-Criteria Approximation Algorithm for k-Means.

[BibT_eX]

[DOI]

Justin Ward

Proceedings of the Approximation, 2016

2015

Concentration inequalities for nonlinear matroid intersection.

[BibT_eX]

[DOI]

Warren Schudy

Random Struct. Algorithms, 2015

Satisfiability of Ordering CSPs Above Average.

[BibT_eX]

[DOI]

Yuan Zhou

CoRR, 2015

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

[BibT_eX]

[DOI]

Shuchi Chawla

Tselil Schramm

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

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

[BibT_eX]

[DOI]

Matthew Caesar

Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, 2015

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Yuan Zhou

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Correlation Clustering with Noisy Partial Information.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Approximation Algorithm for Non-Boolean Max-k-CSP.

[BibT_eX]

[DOI]

Theory Comput., 2014

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm.

[BibT_eX]

[DOI]

Rajsekar Manokaran

ACM Trans. Algorithms, 2014

Min-Max Graph Partitioning and Small Set Expansion.

[BibT_eX]

[DOI]

Nikhil Bansal

Uriel Feige

Robert Krauthgamer

Viswanath Nagarajan

Joseph Naor

Roy Schwartz

SIAM J. Comput., 2014

Optimization Problems with Diseconomies of Scale via Decoupling.

[BibT_eX]

[DOI]

CoRR, 2014

Algorithms for Semi-random Correlation Clustering.

[BibT_eX]

[DOI]

CoRR, 2014

Online Algorithms for Machine Minimization.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Debmalya Panigrahi

CoRR, 2014

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs.

[BibT_eX]

[DOI]

Shuchi Chawla

Tselil Schramm

CoRR, 2014

Constant factor approximation for balanced cut in the PIE model.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximation Algorithm for Sparsest k-Partitioning.

[BibT_eX]

[DOI]

Anand Louis

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Precedence-Constrained Scheduling of Malleable Jobs with Preemption.

[BibT_eX]

[DOI]

Debmalya Panigrahi

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Nonuniform Graph Partitioning with Unrelated Weights.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms.

[BibT_eX]

[DOI]

Niv Buchbinder

Tracy Kimbrel

Retsef Levi

Oper. Res., 2013

Approximation algorithms for spanner problems and Directed Steiner Forest.

[BibT_eX]

[DOI]

Piotr Berman

Arnab Bhattacharyya

Sofya Raskhodnikova

Inf. Comput., 2013

Bilu-Linial Stable Instances of Max Cut

[BibT_eX]

[DOI]

CoRR, 2013

Approximation Algorithm for Sparsest k-Partitioning.

[BibT_eX]

[DOI]

Anand Louis

CoRR, 2013

Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Sorting noisy data with partial information.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Speed regularization and optimality in word classing.

[BibT_eX]

[DOI]

Geoffrey Zweig

Proceedings of the IEEE International Conference on Acoustics, 2013

2012

Chain Independence and Common Information.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2012

Approximation Algorithms for Semi-random Graph Partitioning Problems

[BibT_eX]

[DOI]

CoRR, 2012

Approximation algorithms for semi-random partitioning problems.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms.

[BibT_eX]

[DOI]

Guojing Cong

Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium, 2012

Approximation Algorithm for Non-boolean MAX k-CSP.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Suffix Trees.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Parallel Computing, 2011

How to Play Unique Games against a Semi-Random Adversary

[BibT_eX]

[DOI]

Alexandra Kolla

CoRR, 2011

On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data.

[BibT_eX]

[DOI]

Howard J. Karloff

Flip Korn

Yuval Rabani

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Optimizing Large-Scale Graph Analysis on a Multi-threaded, Multi-core Platform.

[BibT_eX]

[DOI]

Guojing Cong

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes.

[BibT_eX]

[DOI]

Alantha Newman

Proceedings of the Innovations in Computer Science, 2011

Improved Approximation for the Directed Spanner Problem.

[BibT_eX]

[DOI]

Piotr Berman

Arnab Bhattacharyya

Sofya Raskhodnikova

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games.

[BibT_eX]

[DOI]

Alexandra Kolla

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Grothendieck Constant is Strictly Smaller than Krivine's Bound.

[BibT_eX]

[DOI]

Mark Braverman

Assaf Naor

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers.

[BibT_eX]

[DOI]

Matthias Reumann

Proceedings of the 33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 2011

2010

I/O efficient algorithms for serial and parallel suffix tree construction.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2010

Local Global Tradeoffs in Metric Embeddings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Improved Approximation for the Directed Spanner Problem

[BibT_eX]

[DOI]

Arnab Bhattacharyya

CoRR, 2010

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Near-optimal algorithms for maximum constraint satisfaction problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

How to Play Unique Games on Expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Integrality gaps for Sherali-Adams relaxations.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Serial and parallel methods for i/o efficient suffix tree construction.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2009

Indexing genomic sequences on the IBM Blue Gene.

[BibT_eX]

[DOI]

Proceedings of the ACM/IEEE Conference on High Performance Computing, 2009

On Hardness of Pricing Items for Single-Minded Bidders.

[BibT_eX]

[DOI]

Rohit Khandekar

Tracy Kimbrel

Proceedings of the Approximation, 2009

Improving Memory Access Locality for Large-Scale Graph Analysis Applications.

[BibT_eX]

Guojing Cong

Proceedings of the 22nd International Conference on Parallel and Distributed Computing and Communication Systems, 2009

2007

On the Advantage over Random for Maximum Acyclic Subgraph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

A divide and conquer algorithm for d-dimensional arrangement.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Note on MAX 2SAT.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Approximation Algorithm for the Max k-CSP Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Near-optimal algorithms for unique games.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Directed metrics and directed graph partitioning problems.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

How to Play Unique Games Using Embeddings.

[BibT_eX]

[DOI]

Eden Chlamtac

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Conditionally independent random variables

[BibT_eX]

[DOI]

CoRR, 2005

Quadratic forms on graphs.

[BibT_eX]

[DOI]

Noga Alon

Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

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

[BibT_eX]

[DOI]

Amit Agarwal

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2002

A new class of non-Shannon-type inequalities for entropies.

[BibT_eX]

[DOI]