No photo of Konstantin Makarychev

View Scopus Profile

Konstantin Makarychev

  • 1155 Citations
20052024

Research output per year

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

Personal profile

Research Interests

The aim of my research is to introduce new core techniques and design general principles for developing and analyzing algorithms that work in theory and practice. My research interests include approximation algorithms, beyond worst-case analysis, and applications of high-dimension geometry in computer science.

Education/Academic qualification

Mechanics and Mathematics, Lomonosov Moscow State University

Computer Science, PhD, Princeton University

Fingerprint Dive into the research topics where Konstantin Makarychev is active. These topic labels come from the works of this person. Together they form a unique fingerprint.

  • 1 Similar Profiles

Network Recent external collaboration on country level. Dive into details by clicking on the dots.

Grants

HDR TRIPODS: Collaborative Research: Institute for Data, Econometrics, Algorithms and Learning .

Hartline, J. D., Auerbach, E. J., Berry, R. A., Canay, I. A., Guo, D., Horowitz, J. L., Makarychev, K., Vijayaraghavan, A. & Wang, Z.

National Science Foundation

9/15/19 → 8/31/22

Project: Research project

    • Collaborative Research: AF: Medium: Design and Analysis of Models and Algorithms for Real-life Problems

    Makarychev, K.

    National Science Foundation

    7/1/20 → 6/30/24

    Project: Research project

    Research Output

    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 proceeding › Conference contribution

    • 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 journal › Article

    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 proceeding › Conference contribution

    • 2 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 journal › Article

    • 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 journal › Comment/debate