| Publication | Date of Publication | Type |
|---|
| Triplet reconstruction and all other phylogenetic CSPs are approximation resistant | 2025-08-15 | Paper |
| Satisfiability of ordering CSPs above average is fixed-parameter tractable | 2025-08-05 | Paper |
| Solving optimization problems with diseconomies of scale via decoupling | 2025-08-05 | Paper |
| Metric extension operators, vertex sparsifiers and Lipschitz extendability | 2025-04-29 | Paper |
| Approximation algorithm for norm multiway cut | 2025-01-06 | Paper |
| Higher-order Cheeger inequality for partitioning with buffers | 2024-11-28 | Paper |
Batch Optimization for DNA Synthesis
IEEE Transactions on Information Theory | 2024-03-14 | Paper |
Explainable <i>k</i> -means: don’t be greedy, plant bigger trees!
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
| Certified Algorithms: Worst-Case Analysis and Beyond | 2023-02-03 | Paper |
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
SIAM Journal on Computing | 2022-04-01 | Paper |
| Perturbation Resilience | 2022-02-04 | Paper |
| Approximation Algorithms for CSPs | 2021-06-15 | Paper |
| Bilu-Linial stability | 2020-07-10 | Paper |
Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Robust algorithms with polynomial loss for near-unanimity CSPs
SIAM Journal on Computing | 2019-12-09 | Paper |
Nonlinear dimension reduction via outer bi-Lipschitz extensions
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Bilu-Linial stable instances of max cut and minimum multiway cut
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Approximation algorithm for sparsest \(k\)-partitioning
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Concentration inequalities for nonlinear matroid intersection | 2019-05-10 | Paper |
Solving Optimization Problems with Diseconomies of Scale via Decoupling
Journal of the ACM | 2019-02-25 | Paper |
Maximizing polynomials subject to assignment constraints
ACM Transactions on Algorithms | 2018-11-12 | Paper |
Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Robust algorithms with polynomial loss for near-unanimity CSPs
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
A bi-criteria approximation algorithm for \(k\)-means
(available as arXiv preprint) | 2018-04-19 | Paper |
Minimum nonuniform graph partitioning with unrelated weights
Sbornik: Mathematics | 2018-04-06 | Paper |
Algorithms for stable and perturbation-resilient problems
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Chain Independence and Common Information
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Sorting noisy data with partial information
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Local search is better than random assignment for bounded occurrence ordering \(k\)-CSPs
(available as arXiv preprint) | 2017-01-30 | Paper |
Union of Euclidean metric spaces is Euclidean
Discrete Analysis | 2016-10-10 | Paper |
Metric extension operators, vertex sparsifiers and Lipschitz extendability
Israel Journal of Mathematics | 2016-07-25 | Paper |
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Constant factor approximation for balanced cut in the PIE model
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Concentration inequalities for nonlinear matroid intersection
Random Structures & Algorithms | 2015-05-29 | Paper |
Integrality gaps for Sherali-Adams relaxations
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
Theory of Computing | 2015-02-03 | Paper |
| scientific article; zbMATH DE number 6381632 (Why is no real title available?) | 2014-12-18 | Paper |
| A divide and conquer algorithm for \(d\)-dimensional arrangement | 2014-12-18 | Paper |
Near-optimal algorithms for unique games
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Near-optimal algorithms for maximum constraint satisfaction problems
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Min-max Graph Partitioning and Small Set Expansion
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
The Grothendieck Constant is Strictly Smaller than Krivine's Bound
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Min-Max Graph Partitioning and Small Set Expansion
SIAM Journal on Computing | 2014-07-30 | Paper |
Precedence-constrained scheduling of malleable jobs with preemption
Automata, Languages, and Programming | 2014-07-01 | Paper |
Nonuniform graph partitioning with unrelated weights
Automata, Languages, and Programming | 2014-07-01 | Paper |
Online make-to-order joint replenishment model: primal-dual competitive algorithms
Operations Research | 2014-06-26 | Paper |
Approximation algorithms for semi-random partitioning problems
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
| Optimization Problems with Diseconomies of Scale via Decoupling | 2014-04-11 | Paper |
The Grothendieck constant is strictly smaller than Krivine's bound
Forum of Mathematics, Pi | 2014-03-11 | Paper |
Approximation algorithms for spanner problems and directed Steiner forest
Information and Computation | 2013-06-06 | Paper |
Approximation algorithm for non-Boolean MAX \(k\)-CSP
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
| On parsimonious explanations for 2-D tree- and linearly-ordered data | 2012-01-23 | Paper |
Improved approximation for the directed spanner problem
Automata, Languages and Programming | 2011-07-06 | Paper |
Maximizing Polynomials Subject to Assignment Constraints
Automata, Languages and Programming | 2011-07-06 | Paper |
How to Play Unique Games on Expanders
Approximation and Online Algorithms | 2011-02-15 | Paper |
Local global tradeoffs in metric embeddings
SIAM Journal on Computing | 2011-01-17 | Paper |
Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm
Lecture Notes in Computer Science | 2010-09-07 | Paper |
Directed metrics and directed graph partitioning problems
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
\(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Quadratic forms on graphs (extended abstract)
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
| scientific article; zbMATH DE number 5764798 (Why is no real title available?) | 2010-08-06 | Paper |
On Hardness of Pricing Items for Single-Minded Bidders
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
A new class of non-Shannon-type inequalities for entropies
Communications in Information and Systems | 2006-06-20 | Paper |
Quadratic forms on graphs
Inventiones Mathematicae | 2006-03-21 | Paper |
