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

Research Output 2005 2019

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

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

2017
15 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)

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)
2015
16 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
93 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
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
17 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
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
12 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
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

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

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

2010
6 Citations (Scopus)

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

Quadratic Assignment Problem
Approximation algorithms
Linear programming
Labels
Approximation Algorithms
29 Citations (Scopus)

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

Functional analysis
Banach spaces
Mathematical operators
Polynomials
2009
11 Citations (Scopus)

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

Genes
DNA sequences
Parallel algorithms
Data structures
Processing
71 Citations (Scopus)

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

Hardness
14 Citations (Scopus)

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

Hardness
Pricing
Approximation algorithms
Subset
Linear programming
15 Citations (Scopus)

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

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

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

Joint Model
Primal-dual
Primal-dual Algorithm
Online Algorithms
Deterministic Algorithm
2007
5 Citations (Scopus)

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

Divide-and-conquer Algorithm
Arrangement
Costs
Exponent
Minimise
11 Citations (Scopus)

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

23 Citations (Scopus)

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

Constraint satisfaction problems
Constraint Satisfaction Problem
Optimal Algorithm
Semidefinite Programming Relaxation
Rounding
14 Citations (Scopus)

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

Approximation algorithms
2006
18 Citations (Scopus)

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

Metric Graphs
Graph Partitioning
Directed graphs
Directed Graph
Metric
37 Citations (Scopus)

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

Approximation algorithms
Labels
78 Citations (Scopus)

Near-optimal algorithms for unique games

Charikar, M., Makarychev, K. & Makarychev, Y., Sep 5 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Vol. 2006. p. 205-214 10 p.

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

Constraint satisfaction problems
Approximation algorithms