• 1176 Citations
20052020

Research output per year

If you made any changes in Pure these will be visible here soon.

Research Output

2020

Certified algorithms: Worst-case analysis and beyond

Makarychev, K. & Makarychev, Y., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 49. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2019

DNA assembly for nanopore data storage readout

Lopez, R., Chen, Y. J., Dumas Ang, S., Yekhanin, S., Makarychev, K., Racz, M. Z., Seelig, G., Strauss, K. & Ceze, L., Dec 1 2019, In : Nature communications. 10, 1, 2933.

Research output: Contribution to journalArticle

Open Access
4 Scopus citations

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

Makarychev, K., Makarychev, Y. & Razenshteyn, I., Jun 23 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 1027-1038 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Robust algorithms with polynomial loss for near-unanimity CSPs

Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y. & Opršal, J., Jan 1 2019, In : SIAM Journal on Computing. 48, 6, p. 1763-1795 33 p.

Research output: Contribution to journalArticle

2018

Erratum: Random access in large-scale DNA data storage (Nature Biotechnology (2018) 36 (242-248) DOI: 10.1038/nbt.4079)

Organick, L., Ang, S. D., Chen, Y. J., Lopez, R., Yekhanin, S., Makarychev, K., Racz, M. Z., Kamath, G., Gopalan, P., Nguyen, B., Takahashi, C. N., Newman, S., Parker, H. Y., Rashtchian, C., Stewart, K., Gupta, G., Carlson, R., Mulligan, J., Carmean, D., Seelig, G. & 2 others, Ceze, L. & Strauss, K., Jul 6 2018, In : Nature biotechnology. 36, 7, 1 p.

Research output: Contribution to journalComment/debate

Nonlinear dimension reduction via outer Bi-Lipschitz extensions

Mahabadi, S., Makarychev, K., Makarychev, Y. & Razenshteyn, I., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 574-586 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Random access in large-scale DNA data storage

Organick, L., Ang, S. D., Chen, Y. J., Lopez, R., Yekhanin, S., Makarychev, K., Racz, M. Z., Kamath, G., Gopalan, P., Nguyen, B., Takahashi, C. N., Newman, S., Parker, H. Y., Rashtchian, C., Stewart, K., Gupta, G., Carlson, R., Mulligan, J., Carmean, D., Seelig, G. & 2 others, Ceze, L. & Strauss, K., Mar 1 2018, In : Nature biotechnology. 36, 3, p. 242-248 7 p.

Research output: Contribution to journalArticle

70 Scopus citations

Solving optimization problems with diseconomies of scale via decoupling

Makarychev, K. & Sviridenko, M., Nov 2018, In : Journal of the ACM. 65, 6, 42.

Research output: Contribution to journalArticle

1 Scopus citations
2017

Algorithms for stable and perturbation-resilient problems

Angelidakis, H., Makarychev, K. & Makarychev, Y., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 438-451 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Clustering billions of reads for DNA Data storage

Rashtchian, C., Makarychev, K., Rácz, M., Ang, S. D., Jevdjic, D., Yekhanin, S., Ceze, L. & Strauss, K., Jan 1 2017, In : Advances in Neural Information Processing Systems. 2017-December, p. 3361-3372 12 p.

Research output: Contribution to journalConference article

3 Scopus citations

Maximizing polynomials subject to assignment constraints

Makarychev, K. & Sviridenko, M., Nov 1 2017, In : ACM Transactions on Algorithms. 13, 4, 54.

Research output: Contribution to journalArticle

Minimum nonuniform graph partitioning with unrelated weights

Makarychev, K. & Makarychev, Y. S., Jan 1 2017, In : Sbornik Mathematics. 208, 12, p. 1835-1853 19 p.

Research output: Contribution to journalArticle

Robust algorithms with polynomial loss for near-unanimity CSPs

Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y. & Opršal, J., Jan 1 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 340-357 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations
2016

A bi-criteria approximation algorithm for κ-Means

Makarychev, K., Makarychev, Y., Sviridenko, M. & Ward, J., Sep 1 2016, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 60.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

A union of Euclidean metric spaces is Euclidean

Makarychev, K. & Makarychev, Y., Jan 1 2016, In : Discrete Analysis. 14, 2016, p. 1-15 15 p.

Research output: Contribution to journalArticle

2 Scopus citations

Learning communities in the presence of errors

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Jun 6 2016, In : Journal of Machine Learning Research. 49, June, p. 1258-1291 34 p.

Research output: Contribution to journalConference article

8 Scopus citations

Metric extension operators, vertex sparsifiers and Lipschitz extendability

Makarychev, K. & Makarychev, Y., May 1 2016, In : Israel Journal of Mathematics. 212, 2, p. 913-959 47 p.

Research output: Contribution to journalArticle

4 Scopus citations
2015

Concentration inequalities for nonlinear matroid intersection

Makarychev, K., Schudy, W. & Sviridenko, M., May 1 2015, In : Random Structures and Algorithms. 46, 3, p. 541-571 31 p.

Research output: Contribution to journalArticle

1 Scopus citations

Correlation clustering with noisy partial information

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Jan 1 2015, In : Journal of Machine Learning Research. 40, 2015

Research output: Contribution to journalArticle

5 Scopus citations

Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs

Chawla, S., Makarychev, K., Schramm, T. & Yaroslavtsev, G., Jun 14 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 219-228 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Network-aware scheduling for data-parallel jobs: Plan when you can

Jalaparti, V., Bodik, P., Menache, I., Rao, S., Makarychev, K. & Caesar, M., Aug 17 2015, SIGCOMM 2015 - Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. Association for Computing Machinery, Inc, p. 407-420 14 p. (SIGCOMM 2015 - Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

104 Scopus citations

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Makarychev, K., Makarychev, Y. & Zhou, Y., Dec 11 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, Vol. 2015-December. p. 975-993 19 p. 7354438

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations
2014

Approximation algorithm for non-boolean Max-k-CSP

Makarychev, K. & Makarychev, Y., Oct 10 2014, In : Theory of Computing. 10, p. 341-358 18 p.

Research output: Contribution to journalArticle

6 Scopus citations

Approximation algorithm for sparsest k-partitioning

Louis, A. & Makarychev, K., Jan 1 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 1244-1255 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Bilu-linial stable instances of max cut and minimum multiway cut

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Jan 1 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 890-906 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Constant factor approximation for Balanced Cut in the PIE model

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Jan 1 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 41-49 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm

Makarychev, K., Manokaran, R. & Sviridenko, M., Jan 1 2014, In : ACM Transactions on Algorithms. 10, 4, 18.

Research output: Contribution to journalArticle

4 Scopus citations

Min-max graph partitioning and small set expansion

Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J. S. & Schwartz, R., 2014, In : SIAM Journal on Computing. 43, 2, p. 872-904 33 p.

Research output: Contribution to journalArticle

14 Scopus citations

Nonuniform graph partitioning with unrelated weights

Makarychev, K. & Makarychev, Y., Jan 1 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 812-822 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Precedence-constrained scheduling of malleable jobs with preemption

Makarychev, K. & Panigrahi, D., Jan 1 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 823-834 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Solving optimization problems with diseconomies of scale via decoupling

Makarychev, K. & Sviridenko, M., Jan 1 2014, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, p. 571-580 10 p. 6979042

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations
2013

Approximation algorithms for spanner problems and Directed Steiner Forest

Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S. & Yaroslavtsev, G., Jan 1 2013, In : Information and Computation. 222, p. 93-107 15 p.

Research output: Contribution to journalArticle

22 Scopus citations

Local search is better than random assignment for bounded occurrence Ordering k-CSPs

Makarychev, K., Dec 1 2013, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. p. 139-147 9 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 20).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Online make-to-order joint replenishment model: Primal-dual competitive algorithms

Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K. & Sviridenko, M., Jul 1 2013, In : Operations Research. 61, 4, p. 1014-1029 16 p.

Research output: Contribution to journalArticle

12 Scopus citations

Sorting noisy data with partial information

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Feb 11 2013, ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. p. 515-528 14 p. (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Speed regularization and optimality in word classing

Zweig, G. & Makarychev, K., Oct 18 2013, 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings. p. 8237-8241 5 p. 6639271. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

The grothendieck constant is strictly smaller than krivine's bound

Braverman, M., Makarychev, K., Makarychev, Y. & Naor, A., Jan 1 2013, In : Forum of Mathematics, Pi. 1, e4.

Research output: Contribution to journalArticle

17 Scopus citations
2012

Approximation algorithm for non-boolean MAX k-CSP

Makarychev, K. & Makarychev, Y., Aug 28 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 254-265 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Approximation algorithms for semi-random partitioning problems

Makarychev, K., Makarychev, Y. & Vijayaraghavan, A., Jun 26 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 367-384 18 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

Chain independence and common information

Makarychev, K. & Makarychev, Y., Jul 23 2012, In : IEEE Transactions on Information Theory. 58, 8, p. 5279-5286 8 p., 6200860.

Research output: Contribution to journalArticle

1 Scopus citations

Concentration inequalities for nonlinear matroid intersection

Makarychev, K., Schudy, W. & Sviridenko, M., Jan 1 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 420-436 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Open Access

Optimizing large-scale graph analysis on multithreaded, multicore platforms

Cong, G. & Makarychev, K., Oct 4 2012, Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium, IPDPS 2012. p. 414-425 12 p. 6267878

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations
2011

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

Church, P. C., Goscinski, A., Holt, K., Inouye, M., Ghoting, A., Makarychev, K. & Reumann, M., Dec 26 2011, 33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011. p. 924-927 4 p. 6090208. (Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations
4 Scopus citations

How to play unique games against a semi-random adversary: Study of semi-random models of unique games

Kolla, A., Makarychev, K. & Makarychev, Y., Dec 1 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 443-452 10 p. 6108205

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

How to play unique games on expanders

Makarychev, K. & Makarychev, Y., Feb 7 2011, Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. p. 190-200 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6534 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Improved approximation for the directed spanner problem

Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S. & Yaroslavtsev, G., Jul 11 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. p. 1-12 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6755 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Maximizing polynomials subject to assignment constraints

Makarychev, K. & Sviridenko, M., Jul 11 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. p. 510-520 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6755 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Min-max graph partitioning and small set expansion

Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J. & Schwartz, R., Dec 1 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 17-26 10 p. 6108146. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

On parsimonious explanations for 2-D tree- and linearly-ordered data

Karloff, H., Korn, F., Makarychev, K. & Rabani, Y., Dec 1 2011, 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Vol. 9. p. 332-343 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations