Konstantin Makarychev

  • Source: Scopus
20052020

Research output per year

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

Search results

  • 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

    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

    5 Scopus citations
  • 2018

    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

    6 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

    21 Scopus citations
  • Robust algorithms with polynomial loss for near-unanimity CSPs

    Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y. & Opršal, J., 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; vol. 0).

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

    Open Access
    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

    13 Scopus citations
  • 2015

    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

    25 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 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., 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

    22 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
  • 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

    7 Scopus citations
  • Solving optimization problems with diseconomies of scale via decoupling

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

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

    15 Scopus citations
  • 2013

    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
  • 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
  • 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
  • Concentration inequalities for nonlinear matroid intersection

    Makarychev, K., Schudy, W. & Sviridenko, M., 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

    12 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
  • 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

    7 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

    16 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

    32 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
  • Optimizing large-scale graph analysis on a multi-threaded, multi-core platform

    Cong, G. & Makarychev, K., Oct 3 2011, Proceedings - 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011. p. 688-697 10 p. 6012880. (Proceedings - 25th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2011).

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

    16 Scopus citations
  • The Grothendieck constant is strictly smaller than Krivine's bound

    Braverman, M., Makarychev, K., Makarychev, Y. & Naor, A., Dec 1 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 453-462 10 p. 6108206. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    21 Scopus citations
  • 2010

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

    Makarychev, K., Manokaran, R. & Sviridenko, M., Aug 12 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 594-604 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

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

    9 Scopus citations
  • Metric extension operators, vertex sparsifiers and Lipschitz extendability

    Makarychev, K. & Makarychev, Y., Dec 1 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. p. 255-264 10 p. 5671173. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    31 Scopus citations
  • 2009

    Indexing genomic sequences on the IBM Blue Gene

    Ghoting, A. & Makarychev, K., Dec 1 2009, Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC '09. 1654122. (Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC '09).

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

    13 Scopus citations
  • Integrality gaps for sherali-adams relaxations

    Charikar, M., Makarychev, K. & Makarychev, Y., Nov 9 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 283-292 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    74 Scopus citations
  • On hardness of pricing items for single-minded bidders

    Khandekar, R., Kimbrel, T., Makarychev, K. & Sviridenko, M., Nov 6 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 202-216 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

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

    14 Scopus citations
  • Serial and parallel methods for I/O efficient suffix tree construction

    Ghoting, A. & Makarychev, K., Dec 4 2009, SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems. p. 827-840 14 p. (SIGMOD-PODS'09 - Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems).

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

    18 Scopus citations
  • 2008

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

    Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K. & Sviridenko, M., Dec 1 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 952-961 10 p.

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

    20 Scopus citations
  • 2007

    A divide and conquer algorithm for d-dimensional arrangement

    Charikar, M., Makarychev, K. & Makarychev, Y., Jan 1 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 541-546 6 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

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

    5 Scopus citations
  • Local global tradeoffs in metric embeddings

    Charikar, M., Makarychev, K. & Makarychev, Y., Dec 1 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 713-723 11 p. 4389539. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    11 Scopus citations
  • Near-optimal algorithms for maximum constraint satisfaction problems

    Charikar, M., Makarychev, K. & Makarychev, Y., Jan 1 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 62-68 7 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

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

    23 Scopus citations
  • On the advantage over random for maximum acyclic subgraph

    Charikar, M., Makarychev, K. & Makarychev, Y., Dec 1 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 625-633 9 p. 4389531. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    15 Scopus citations
  • 2006

    Directed metrics and directed graph partitioning problems

    Charikar, M., Makarychev, K. & Makarychev, Y., Feb 28 2006, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 51-60 10 p.

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

    20 Scopus citations
  • How to play unique games using embeddings

    Chlamtac, E., Makarychev, K. & Makarychev, Y., Dec 1 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 687-696 10 p. 4031403. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

    38 Scopus citations
  • Near-optimal algorithms for unique games

    Charikar, M., Makarychev, K. & Makarychev, Y., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 205-214 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

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

    83 Scopus citations