• 1191 Citations
20052020

Research output per year

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

Research Output

Filter
Article
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
5 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

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

77 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

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

2016

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

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

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

23 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

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

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
2011
4 Scopus citations
2010

I/O efficient algorithms for serial and parallel suffix tree construction

Ghoting, A. & Makarychev, K., Nov 1 2010, In : ACM Transactions on Database Systems. 35, 4, 25.

Research output: Contribution to journalArticle

7 Scopus citations

Local global tradeoffs in metric embeddings

Charikar, M., Makarychev, K. & Makarychev, Y., May 19 2010, In : SIAM Journal on Computing. 39, 6, p. 2487-2512 26 p.

Research output: Contribution to journalArticle

12 Scopus citations
2009

Near-optimal algorithms for maximum constraint satisfaction problems

Charikar, M., Makarychev, K. & Makarychev, Y., Jul 1 2009, In : ACM Transactions on Algorithms. 5, 3, 32.

Research output: Contribution to journalArticle

29 Scopus citations