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

Research Output 2005 2019

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

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

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
2011
4 Citations (Scopus)
Sequence Alignment
Supercomputers
Genes
Genome
Data storage equipment
2010
7 Citations (Scopus)

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

Genes
Data storage equipment
Trees (mathematics)
Data structures
Scalability
12 Citations (Scopus)

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

Metric Embeddings
Trade-offs
Lower bound
Lift-and-project
Graph Partitioning
2009
28 Citations (Scopus)

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

Constraint Satisfaction Problem
Optimal Algorithm
Semidefinite Programming Relaxation
Rounding
Approximation