| Publication | Date of Publication | Type |
|---|
| Higher degree sum-of-squares relaxations robust against oblivious outliers | 2024-05-14 | Paper |
| Algorithms approaching the threshold for semi-random planted clique | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788362 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Playing unique games on certified small-set expanders
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Small-set expansion in shortcode graph and the 2-to-2 conjecture
(available as arXiv preprint) | 2022-07-18 | Paper |
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
Robust moment estimation and improved clustering via sum of squares
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
| Towards computing the Grothendieck constant | 2019-05-06 | Paper |
An asymptotic approximation scheme for multigraph edge coloring
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Approximate Constraint Satisfaction Requires Large LP Relaxations
Journal of the ACM | 2018-08-02 | Paper |
Subexponential algorithms for unique games and related problems
Journal of the ACM | 2018-08-02 | Paper |
Sum-of-squares proofs and the quest toward optimal algorithms
(available as arXiv preprint) | 2017-11-06 | Paper |
| Bayesian estimation from few samples: community detection and related problems | 2017-09-30 | Paper |
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| Subsampling mathematical relaxations and average-case complexity | 2017-09-29 | Paper |
Quantum entanglement, sum of squares, and the log rank conjecture
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Message-Passing Algorithms and Improved LP Decoding
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Approximation Limits of Linear Programs (Beyond Hierarchies)
Mathematics of Operations Research | 2015-11-04 | Paper |
Making the Long Code Shorter
SIAM Journal on Computing | 2015-11-04 | Paper |
Lower bounds on the size of semidefinite programming relaxations
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Dictionary learning and tensor decomposition via the sum-of-squares method
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Analytical approach to parallel repetition
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Rounding sum-of-squares relaxations
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
A parallel repetition theorem for entangled projection games
Computational Complexity | 2015-06-23 | Paper |
A parallel repetition theorem for entangled projection games
Computational Complexity | 2015-06-23 | Paper |
Message passing algorithms and improved LP decoding
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
| An asymptotic approximation scheme for multigraph edge coloring | 2014-10-13 | Paper |
Approximations for the isoperimetric and spectral profile of graphs and related parameters
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Graph expansion and the unique games conjecture
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Rounding Semidefinite Programming Hierarchies via Global Correlation
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
How to Round Any CSP
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
| Fast SDP algorithms for constraint satisfaction problems | 2014-05-22 | Paper |
Hypercontractivity, sum-of-squares proofs, and their applications
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Improved Rounding for Parallel Repeated Unique Games
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Towards a Study of Low-Complexity Graphs
Automata, Languages and Programming | 2009-07-14 | Paper |
| Unique games on expanding constraint graphs are easy (extended abstract) | 2009-01-05 | Paper |
Asymptotically Optimal Hitting Sets Against Polynomials
Automata, Languages and Programming | 2008-08-28 | Paper |
The Interval Liar Game
Algorithms and Computation | 2008-04-24 | Paper |
The Interval Liar Game
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
