Konstantin Makarychev

141 papers A* 46A 10B 2Misc 1Journal 66Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	—	`conf`	A Simple Average-case Analysis of Recursive Randomized Greedy MIS. SOSA Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
2025	A*	`conf`	Constraint Satisfaction Problems with Advice. SODA Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
2025	J	`jnl`	Dynamic Algorithm for Explainable k-medians Clustering under lp Norm. CoRR Konstantin Makarychev, Ilias Papanikolaou, Liren Shan
2025	J	`jnl`	SPARSE-PIVOT: Dynamic correlation clustering for node insertions. CoRR Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
2025	A*	`conf`	Sparse-pivot: Dynamic correlation clustering for node insertions. ICML Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
2024	A*	`conf`	Approximation Scheme for Weighted Metric Clustering via Sherali-Adams. AAAI Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
2024	J	`jnl`	Constraint Satisfaction Problems with Advice. CoRR Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
2024	A*	`conf`	Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2024	A*	`conf`	Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. ICML Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
2024	J	`jnl`	Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. CoRR Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovic
2023	A	`conf`	Approximation Algorithm for Norm Multiway Cut. ESA Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
2023	J	`jnl`	Approximation Algorithms for Norm Multiway Cut. CoRR Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan
2023	J	`jnl`	Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2023	A*	`conf`	Random Cuts are Optimal for Explainable k-Medians. NeurIPS Konstantin Makarychev, Liren Shan
2023	J	`jnl`	Random Cuts are Optimal for Explainable k-Medians. CoRR Konstantin Makarychev, Liren Shan
2023	A*	`conf`	Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! NeurIPS Konstantin Makarychev, Sayak Chakrabarty
2023	J	`jnl`	Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! CoRR Sayak Chakrabarty, Konstantin Makarychev
2023	A*	`conf`	Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant. FOCS Vaggos Chatziafratis, Konstantin Makarychev
2022	J	`jnl`	Batch Optimization for DNA Synthesis. IEEE Trans. Inf. Theory Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
2022	A*	`conf`	Explainable STOC Konstantin Makarychev, Liren Shan
2022	J	`jnl`	Phylogenetic CSPs are Approximation Resistant. CoRR Vaggos Chatziafratis, Konstantin Makarychev
2021	B	`conf`	Batch Optimization for DNA Synthesis. ISIT Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
2021	J	`jnl`	Correlation Clustering with Asymmetric Classification Errors. CoRR Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	J	`jnl`	Explainable k-means. Don't be greedy, plant bigger trees! CoRR Konstantin Makarychev, Liren Shan
2021	A*	`conf`	Local Correlation Clustering with Asymmetric Classification Errors. ICML Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	J	`jnl`	Local Correlation Clustering with Asymmetric Classification Errors. CoRR Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2021	A*	`conf`	Near-Optimal Algorithms for Explainable k-Medians and k-Means. ICML Konstantin Makarychev, Liren Shan
2021	J	`jnl`	Near-optimal Algorithms for Explainable k-Medians and k-Means. CoRR Konstantin Makarychev, Liren Shan
2021	A*	`conf`	Two-Sided Kirszbraun Theorem. SoCG Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev
2020	J	`jnl`	Batch Optimization for DNA Synthesis. CoRR Konstantin Makarychev, Miklós Z. Rácz, Cyrus Rashtchian, Sergey Yekhanin
2020	A	`conf`	Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. AISTATS Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, Mohammad Mahdian
2020	A	`conf`	Certified Algorithms: Worst-Case Analysis and Beyond. ITCS Konstantin Makarychev, Yury Makarychev
2020	A*	`conf`	Correlation Clustering with Asymmetric Classification Errors. ICML Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury Makarychev
2020	A*	`conf`	Improved Guarantees for k-means++ and k-means++ Parallel. NeurIPS Konstantin Makarychev, Aravind Reddy, Liren Shan
2020	J	`jnl`	Improved Guarantees for k-means++ and k-means++ Parallel. CoRR Konstantin Makarychev, Aravind Reddy, Liren Shan
2020	—	`ch.`	Perturbation Resilience. Beyond the Worst-Case Analysis of Algorithms Konstantin Makarychev, Yury Makarychev
2020	A*	`ed.`	Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 STOC Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
2019	J	`jnl`	Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection. CoRR Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, Grigory Yaroslavtsev
2019	A*	`conf`	Correlation clustering with local objectives. NeurIPS Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
2019	J	`jnl`	Improved algorithms for Correlation Clustering with local objectives. CoRR Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou
2019	J	`jnl`	Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. SIAM J. Comput. Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2019	A*	`conf`	Performance of Johnson-Lindenstrauss transform for STOC Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2019	J	`jnl`	Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2018	J	`jnl`	Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions. CoRR Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2018	A*	`conf`	Nonlinear dimension reduction via outer Bi-Lipschitz extensions. STOC Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2018	J	`jnl`	Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering. CoRR Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn
2018	J	`jnl`	Solving Optimization Problems with Diseconomies of Scale via Decoupling. J. ACM Konstantin Makarychev, Maxim Sviridenko
2017	A*	`conf`	Algorithms for stable and perturbation-resilient problems. STOC Haris Angelidakis, Konstantin Makarychev, Yury Makarychev
2017	—	`ch.`	Approximation Algorithms for CSPs. The Constraint Satisfaction Problem Konstantin Makarychev, Yury Makarychev
2017	—	`conf`	Clustering Billions of Reads for DNA Data Storage. NIPS Cyrus Rashtchian, Konstantin Makarychev, Miklós Z. Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, Karin Strauss
2017	J	`jnl`	Maximizing Polynomials Subject to Assignment Constraints. ACM Trans. Algorithms Konstantin Makarychev, Maxim Sviridenko
2017	A*	`conf`	Robust algorithms with polynomial loss for near-unanimity CSPs. SODA Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016	—	`conf`	A Bi-Criteria Approximation Algorithm for k-Means. APPROX-RANDOM Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
2016	A*	`conf`	Learning Communities in the Presence of Errors. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2016	J	`jnl`	Metric Perturbation Resilience. CoRR Konstantin Makarychev, Yury Makarychev
2016	J	`jnl`	Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2015	J	`jnl`	A bi-criteria approximation algorithm for k Means. CoRR Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward
2015	J	`jnl`	Concentration inequalities for nonlinear matroid intersection. Random Struct. Algorithms Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
2015	A*	`conf`	Correlation Clustering with Noisy Partial Information. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	J	`jnl`	Learning Communities in the Presence of Errors. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	A*	`conf`	Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. STOC Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
2015	A*	`conf`	Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. SIGCOMM Virajith Jalaparti, Peter Bodík, Ishai Menache, Sriram Rao, Konstantin Makarychev, Matthew Caesar
2015	J	`jnl`	Satisfiability of Ordering CSPs Above Average. CoRR Konstantin Makarychev, Yury Makarychev, Yuan Zhou
2015	A*	`conf`	Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. FOCS Konstantin Makarychev, Yury Makarychev, Yuan Zhou
2014	J	`jnl`	Algorithms for Semi-random Correlation Clustering. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Approximation Algorithm for Non-Boolean Max- Theory Comput. Konstantin Makarychev, Yury Makarychev
2014	A*	`conf`	Approximation Algorithm for Sparsest SODA Anand Louis, Konstantin Makarychev
2014	A*	`conf`	Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Constant Factor Approximation for Balanced Cut in the PIE model. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	A*	`conf`	Constant factor approximation for balanced cut in the PIE model. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm. CoRR Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
2014	J	`jnl`	Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm. ACM Trans. Algorithms Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
2014	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2014	J	`jnl`	Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. CoRR Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
2014	—	`conf`	Nonuniform Graph Partitioning with Unrelated Weights. ICALP (1) Konstantin Makarychev, Yury Makarychev
2014	J	`jnl`	Nonuniform Graph Partitioning with Unrelated Weights. CoRR Konstantin Makarychev, Yury Makarychev
2014	J	`jnl`	Online Algorithms for Machine Minimization. CoRR Nikhil R. Devanur, Konstantin Makarychev, Debmalya Panigrahi, Grigory Yaroslavtsev
2014	J	`jnl`	Optimization Problems with Diseconomies of Scale via Decoupling. CoRR Konstantin Makarychev, Maxim Sviridenko
2014	—	`conf`	Precedence-Constrained Scheduling of Malleable Jobs with Preemption. ICALP (1) Konstantin Makarychev, Debmalya Panigrahi
2014	J	`jnl`	Precedence-constrained Scheduling of Malleable Jobs with Preemption. CoRR Konstantin Makarychev, Debmalya Panigrahi
2014	A*	`conf`	Solving Optimization Problems with Diseconomies of Scale via Decoupling. FOCS Konstantin Makarychev, Maxim Sviridenko
2013	J	`jnl`	Approximation Algorithm for Sparsest k-Partitioning. CoRR Anand Louis, Konstantin Makarychev
2013	J	`jnl`	Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
2013	J	`jnl`	Bilu-Linial Stable Instances of Max Cut CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	A	`conf`	Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. STACS Konstantin Makarychev
2013	J	`jnl`	Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms. Oper. Res. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko
2013	A	`conf`	Sorting noisy data with partial information. ITCS Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	Misc	`conf`	Speed regularization and optimality in word classing. ICASSP Geoffrey Zweig, Konstantin Makarychev
2012	J	`jnl`	Approximation Algorithm for Non-Boolean MAX k-CSP CoRR Konstantin Makarychev, Yury Makarychev
2012	—	`conf`	Approximation Algorithm for Non-boolean MAX k-CSP. APPROX-RANDOM Konstantin Makarychev, Yury Makarychev
2012	J	`jnl`	Approximation Algorithms for Semi-random Graph Partitioning Problems CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	A*	`conf`	Approximation algorithms for semi-random partitioning problems. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	J	`jnl`	Chain Independence and Common Information. IEEE Trans. Inf. Theory Konstantin Makarychev, Yury Makarychev
2012	A*	`conf`	Concentration inequalities for nonlinear matroid intersection. SODA Konstantin Makarychev, Warren Schudy, Maxim Sviridenko
2012	J	`jnl`	Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs CoRR Konstantin Makarychev
2012	A	`conf`	Optimizing Large-scale Graph Analysis on Multithreaded, Multicore Platforms. IPDPS Guojing Cong, Konstantin Makarychev
2011	A	`conf`	Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. ICS Konstantin Makarychev, Alantha Newman
2011	—	`conf`	Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers. EMBC Philip C. Church, Andrzej Goscinski, Kathryn E. Holt, Michael Inouye, Amol Ghoting, Konstantin Makarychev, Matthias Reumann
2011	A*	`conf`	How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. FOCS Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
2011	J	`jnl`	How to Play Unique Games against a Semi-Random Adversary CoRR Alexandra Kolla, Konstantin Makarychev, Yury Makarychev
2011	—	`conf`	Improved Approximation for the Directed Spanner Problem. ICALP (1) Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev
2011	—	`conf`	Maximizing Polynomials Subject to Assignment Constraints. ICALP (1) Konstantin Makarychev, Maxim Sviridenko
2011	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion CoRR Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A*	`conf`	Min-max Graph Partitioning and Small Set Expansion. FOCS Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A	`conf`	On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. STACS Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
2011	J	`jnl`	On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data CoRR Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani
2011	A	`conf`	Optimizing Large-Scale Graph Analysis on a Multi-threaded, Multi-core Platform. IPDPS Guojing Cong, Konstantin Makarychev
2011	—	`ch.`	Suffix Trees. Encyclopedia of Parallel Computing Amol Ghoting, Konstantin Makarychev
2011	A*	`conf`	The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2011	J	`jnl`	The Grothendieck constant is strictly smaller than Krivine's bound. CoRR Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2010	B	`conf`	How to Play Unique Games on Expanders. WAOA Konstantin Makarychev, Yury Makarychev
2010	J	`jnl`	I/O efficient algorithms for serial and parallel suffix tree construction. ACM Trans. Database Syst. Amol Ghoting, Konstantin Makarychev
2010	J	`jnl`	Improved Approximation for the Directed Spanner Problem CoRR Arnab Bhattacharyya, Konstantin Makarychev
2010	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2010	—	`conf`	Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm. ICALP (1) Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
2010	J	`jnl`	Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability CoRR Konstantin Makarychev, Yury Makarychev
2010	A*	`conf`	Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. FOCS Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	How to Play Unique Games on Expanders CoRR Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	How to Play Unique Games on Expanders. Electron. Colloquium Comput. Complex. Konstantin Makarychev, Yury Makarychev
2009	—	`conf`	Improving Memory Access Locality for Large-Scale Graph Analysis Applications. PDCCS Guojing Cong, Konstantin Makarychev
2009	A	`conf`	Indexing genomic sequences on the IBM Blue Gene. SC Amol Ghoting, Konstantin Makarychev
2009	A*	`conf`	Integrality gaps for Sherali-Adams relaxations. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2009	J	`jnl`	Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms Moses Charikar, Konstantin Makarychev, Yury Makarychev
2009	—	`conf`	On Hardness of Pricing Items for Single-Minded Bidders. APPROX-RANDOM Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko
2009	—	`conf`	Serial and parallel methods for i/o efficient suffix tree construction. SIGMOD Conference Amol Ghoting, Konstantin Makarychev
2008	A*	`conf`	Online make-to-order joint replenishment model: primal dual competitive algorithms. SODA Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko
2007	A*	`conf`	A divide and conquer algorithm for SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Local Global Tradeoffs in Metric Embeddings. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	Local Global Tradeoffs in Metric Embeddings. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	Near-optimal algorithms for maximum constraint satisfaction problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	A*	`conf`	On the Advantage over Random for Maximum Acyclic Subgraph. FOCS Moses Charikar, Konstantin Makarychev, Yury Makarychev
2007	J	`jnl`	On the Advantage over Random for Maximum Acyclic Subgraph. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	Approximation Algorithm for the Max k-CSP Problem. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	Directed metrics and directed graph partitioning problems. SODA Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	How to Play Unique Games Using Embeddings. FOCS Eden Chlamtac, Konstantin Makarychev, Yury Makarychev
2006	A*	`conf`	Near-optimal algorithms for unique games. STOC Moses Charikar, Konstantin Makarychev, Yury Makarychev
2006	J	`jnl`	Note on MAX 2SAT. Electron. Colloquium Comput. Complex. Moses Charikar, Konstantin Makarychev, Yury Makarychev
2005	J	`jnl`	Conditionally independent random variables CoRR Konstantin Makarychev, Yury Makarychev
2005	A*	`conf`	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. STOC Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev
2005	A*	`conf`	Quadratic forms on graphs. STOC Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
2002	J	`jnl`	A new class of non-Shannon-type inequalities for entropies. Commun. Inf. Syst. Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, Nikolai K. Vereshchagin