Konstantin Makarychev

Affiliations:
  • Northwestern University, IL, USA
  • Princeton University, USA (former)


According to our database1, Konstantin Makarychev authored at least 93 papers between 2002 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Higher-Order Cheeger Inequality for Partitioning with Buffers.
CoRR, 2023

Approximation Algorithms for Norm Multiway Cut.
CoRR, 2023

Random Cuts are Optimal for Explainable k-Medians.
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!
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.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Approximation Algorithm for Norm Multiway Cut.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022
Batch Optimization for DNA Synthesis.
IEEE Trans. Inf. Theory, 2022

Phylogenetic CSPs are Approximation Resistant.
CoRR, 2022

Explainable <i>k</i>-means: don't be greedy, plant bigger trees!
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!
CoRR, 2021

Near-Optimal Algorithms for Explainable k-Medians and k-Means.
Proceedings of the 38th International Conference on Machine Learning, 2021

Local Correlation Clustering with Asymmetric Classification Errors.
Proceedings of the 38th International Conference on Machine Learning, 2021

Two-Sided Kirszbraun Theorem.
Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020
Improved Guarantees for k-means++ and k-means++ Parallel.
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.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Correlation Clustering with Asymmetric Classification Errors.
Proceedings of the 37th International Conference on Machine Learning, 2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Perturbation Resilience.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput., 2019

Improved algorithms for Correlation Clustering with local objectives.
CoRR, 2019

Performance of Johnson-Lindenstrauss transform for <i>k</i>-means and <i>k</i>-medians clustering.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Correlation clustering with local objectives.
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.
J. ACM, 2018

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

Nonlinear dimension reduction via outer Bi-Lipschitz extensions.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017
Maximizing Polynomials Subject to Assignment Constraints.
ACM Trans. Algorithms, 2017

Algorithms for stable and perturbation-resilient problems.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Clustering Billions of Reads for DNA Data Storage.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximation Algorithms for CSPs.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
Metric Perturbation Resilience.
CoRR, 2016

Learning Communities in the Presence of Errors.
Proceedings of the 29th Conference on Learning Theory, 2016

A Bi-Criteria Approximation Algorithm for k-Means.
Proceedings of the Approximation, 2016

2015
Concentration inequalities for nonlinear matroid intersection.
Random Struct. Algorithms, 2015

Satisfiability of Ordering CSPs Above Average.
CoRR, 2015

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs.
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.
Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, 2015

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Correlation Clustering with Noisy Partial Information.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Approximation Algorithm for Non-Boolean Max-<i>k</i>-CSP.
Theory Comput., 2014

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm.
ACM Trans. Algorithms, 2014

Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 2014

Optimization Problems with Diseconomies of Scale via Decoupling.
CoRR, 2014

Algorithms for Semi-random Correlation Clustering.
CoRR, 2014

Online Algorithms for Machine Minimization.
CoRR, 2014

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

Constant factor approximation for balanced cut in the PIE model.
Proceedings of the Symposium on Theory of Computing, 2014

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximation Algorithm for Sparsest <i>k</i>-Partitioning.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Precedence-Constrained Scheduling of Malleable Jobs with Preemption.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Nonuniform Graph Partitioning with Unrelated Weights.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms.
Oper. Res., 2013

Approximation algorithms for spanner problems and Directed Steiner Forest.
Inf. Comput., 2013

Bilu-Linial Stable Instances of Max Cut
CoRR, 2013

Approximation Algorithm for Sparsest k-Partitioning.
CoRR, 2013

Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Sorting noisy data with partial information.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Speed regularization and optimality in word classing.
Proceedings of the IEEE International Conference on Acoustics, 2013

2012
Chain Independence and Common Information.
IEEE Trans. Inf. Theory, 2012

Approximation Algorithms for Semi-random Graph Partitioning Problems
CoRR, 2012

Approximation algorithms for semi-random partitioning problems.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms.
Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium, 2012

Approximation Algorithm for Non-boolean MAX k-CSP.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Suffix Trees.
Proceedings of the Encyclopedia of Parallel Computing, 2011

How to Play Unique Games against a Semi-Random Adversary
CoRR, 2011

On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data.
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.
Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes.
Proceedings of the Innovations in Computer Science, 2011

Improved Approximation for the Directed Spanner Problem.
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.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Grothendieck Constant is Strictly Smaller than Krivine's Bound.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers.
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.
ACM Trans. Database Syst., 2010

Improved Approximation for the Directed Spanner Problem
CoRR, 2010

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Near-optimal algorithms for maximum constraint satisfaction problems.
ACM Trans. Algorithms, 2009

How to Play Unique Games on Expanders.
Electron. Colloquium Comput. Complex., 2009

Integrality gaps for Sherali-Adams relaxations.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Serial and parallel methods for i/o efficient suffix tree construction.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2009

Indexing genomic sequences on the IBM Blue Gene.
Proceedings of the ACM/IEEE Conference on High Performance Computing, 2009

On Hardness of Pricing Items for Single-Minded Bidders.
Proceedings of the Approximation, 2009

Improving Memory Access Locality for Large-Scale Graph Analysis Applications.
Proceedings of the 22nd International Conference on Parallel and Distributed Computing and Communication Systems, 2009

2007
Local Global Tradeoffs in Metric Embeddings.
Electron. Colloquium Comput. Complex., 2007

On the Advantage over Random for Maximum Acyclic Subgraph.
Electron. Colloquium Comput. Complex., 2007

A divide and conquer algorithm for <i>d</i>-dimensional arrangement.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Note on MAX 2SAT.
Electron. Colloquium Comput. Complex., 2006

Approximation Algorithm for the Max k-CSP Problem.
Electron. Colloquium Comput. Complex., 2006

Near-optimal algorithms for unique games.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Directed metrics and directed graph partitioning problems.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

How to Play Unique Games Using Embeddings.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Conditionally independent random variables
CoRR, 2005

Quadratic forms on graphs.
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.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2002
A new class of non-Shannon-type inequalities for entropies.
Commun. Inf. Syst., 2002


  Loading...