• 1047 Citations
20052022
If you made any changes in Pure, your changes will be visible here soon.

Research Output 2005 2019

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
Nanopores
Information Storage and Retrieval
data storage
readout
sequencing

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

Costs
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

HTML
Information Storage and Retrieval
Bacilli
Biotechnology
Bacillus subtilis
3 Citations (Scopus)

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

45 Citations (Scopus)

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

Information Storage and Retrieval
DNA
Data storage equipment
Oligonucleotides
Libraries
1 Citation (Scopus)

Solving optimization problems with diseconomies of scale via decoupling

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

Research output: Contribution to journalArticle

Random variables
Approximation algorithms
Linear programming
Resource allocation
Costs
2017
14 Citations (Scopus)

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

Combinatorial optimization
Polynomials
Hardness
3 Citations (Scopus)

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

DNA
Data storage equipment
DNA sequences
Parallel algorithms
Scalability

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

Assignment Problem
Approximation Algorithms
Assignment
LP Relaxation
Triangle inequality

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

Graph Partitioning
Pi
Bicriteria
Approximation Algorithms
Graph in graph theory
3 Citations (Scopus)

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

Robust Algorithm
Constraint satisfaction problems
Polynomials
Constraint Satisfaction Problem
Polynomial
2016
7 Citations (Scopus)

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

Approximation algorithms
Linear programming
Costs
Polynomials
Local search (optimization)
2 Citations (Scopus)

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

Metric space
Euclidean
Union
Euclidean space
Open Problems
5 Citations (Scopus)

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

Recovery
Modeling Error
Model
Community Detection
Kullback-Leibler Divergence
3 Citations (Scopus)

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

Extension Operator
Extendability
Lipschitz
Metric
Vertex of a graph
2015
1 Citation (Scopus)

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

Matroid Intersection
Concentration Inequalities
Scheduling
Polynomials
Randomized Rounding
5 Citations (Scopus)

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

Partial Information
Clustering
Approximation algorithms
Costs
Approximation Algorithms
15 Citations (Scopus)

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

Approximation algorithms
Linear programming
92 Citations (Scopus)

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

scheduling
Yarn
Scheduling
workload
Bandwidth
1 Citation (Scopus)

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

Constraint satisfaction problems
Linear equations
Decomposition
Atoms
2014
6 Citations (Scopus)

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

Approximation algorithms
Approximation Algorithms
Asymptotically Optimal
Predicate
Polynomial-time Algorithm
10 Citations (Scopus)

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.

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

Approximation algorithms
Approximation Algorithms
Partitioning
Partition
Bicriteria
16 Citations (Scopus)

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

Multiway Cut
Max-cut
Minimum Cut
Polynomials
Polynomial-time Algorithm
11 Citations (Scopus)

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

Approximation algorithms
Costs
3 Citations (Scopus)

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

Quadratic Assignment Problem
Approximation Algorithms
Cover
Graph Isomorphism
Linear Programming Relaxation
12 Citations (Scopus)

Min-max graph partitioning and small set expansion

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

Research output: Contribution to journalArticle

Graph Partitioning
Approximation algorithms
Min-max
Approximation Algorithms
Graph in graph theory
4 Citations (Scopus)

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

Graph Partitioning
Pi
Approximation algorithms
Partition
Graph in graph theory
6 Citations (Scopus)

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

Preemption
Scheduling
Processing
Precedence Constraints
Job Scheduling
10 Citations (Scopus)

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

Random variables
Approximation algorithms
Linear programming
Resource allocation
Costs
2013
18 Citations (Scopus)

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

Spanner
Approximation algorithms
Approximation Algorithms
Directed graphs
Subgraph
2 Citations (Scopus)

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

9 Citations (Scopus)

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

Linear programming
Supply chains
Make-to-order
Joint replenishment
Planning
7 Citations (Scopus)

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

Sorting
Approximation algorithms
Costs
Directed graphs
Partial information
17 Citations (Scopus)

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

Recurrent neural networks
Dynamic programming
14 Citations (Scopus)

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

Strictly
Rounding
Approximation Algorithms
Hyperplane
Polynomial-time Algorithm
2012
5 Citations (Scopus)

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

Approximation algorithms
Approximation Algorithms
Asymptotically Optimal
Predicate
Polynomial-time Algorithm
26 Citations (Scopus)

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

Approximation algorithms

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

Random variables

Concentration inequalities for nonlinear matroid intersection

Makarychev, K., Schudy, W. & Sviridenko, M., Apr 30 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. p. 420-436 17 p.

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

Matroid Intersection
Concentration Inequalities
Scheduling
Polynomials
Randomized Rounding
10 Citations (Scopus)

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

Data storage equipment
Sun
Computer hardware
Masks
Scheduling
2011
2 Citations (Scopus)

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

Sequence Alignment
Supercomputers
Genes
Genome
Data storage equipment
4 Citations (Scopus)
Sequence Alignment
Supercomputers
Genes
Genome
Data storage equipment
14 Citations (Scopus)

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

Polynomials
6 Citations (Scopus)

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

Expander
Game
Smallest Eigenvalue
Assignment
Graph in graph theory
14 Citations (Scopus)

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

Spanner
Approximation
Graph in graph theory
Subgraph
Directed graphs

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

Approximation algorithms
Assignment Problem
Approximation Algorithms
Assignment
Polynomials
29 Citations (Scopus)

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

Approximation algorithms
2 Citations (Scopus)

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

Approximation algorithms
Computational complexity
Semantics
15 Citations (Scopus)

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

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

Data storage equipment
Computer hardware
Masks
Costs
18 Citations (Scopus)

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

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