| Publication | Date of Publication | Type |
|---|
| New SDP roundings and certifiable approximation for cubic optimization | 2024-11-28 | Paper |
| Approximating max-cut on bounded degree graphs: tighter analysis of the FKL algorithm | 2024-11-14 | Paper |
| Ellipsoid fitting up to a constant | 2024-11-14 | Paper |
| Bypassing the XOR trick: stronger certificates for hypergraph clique number | 2024-08-22 | Paper |
| Public-key encryption, local pseudorandom generators, and the low-degree method | 2024-08-01 | Paper |
| Algorithmic thresholds for refuting random polynomial systems | 2024-07-19 | Paper |
| A moment-matching approach to testable learning and a new characterization of Rademacher complexity | 2024-05-08 | Paper |
| Algorithms approaching the threshold for semi-random planted clique | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788366 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788416 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Robustly learning mixtures of k arbitrary Gaussians
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
List-decodable covariance estimation
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Memory-Sample Lower Bounds for Learning Parity with Noise
(available as arXiv preprint) | 2023-11-20 | 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 |
scientific article; zbMATH DE number 7758323 (Why is no real title available?)
(available as arXiv preprint) | 2023-10-31 | Paper |
| A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation | 2023-08-29 | Paper |
A stress-free sum-of-squares lower bound for coloring
(available as arXiv preprint) | 2023-07-12 | Paper |
| Ellipsoid Fitting Up to a Constant | 2023-07-12 | Paper |
| Privately Estimating a Gaussian: Efficient, Robust and Optimal | 2022-12-15 | Paper |
| A simple and sharper proof of the hypergraph Moore bound | 2022-07-21 | Paper |
Small-set expansion in shortcode graph and the 2-to-2 conjecture
(available as arXiv preprint) | 2022-07-18 | Paper |
scientific article; zbMATH DE number 7559092 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
SIAM Journal on Computing | 2021-06-22 | Paper |
| Improper learning by refuting | 2021-06-15 | Paper |
Semialgebraic Proofs and Efficient Algorithm Design
Foundations and Trends® in Theoretical Computer Science | 2020-02-13 | Paper |
| Sum-of-squares meets program obfuscation, revisited | 2020-02-04 | Paper |
Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
Theoretical Computer Science | 2020-01-29 | 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 |
Sum-of-squares meets Nash: lower bounds for finding any equilibrium
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Testing surface area
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Submodular functions are noise stable | 2019-05-10 | Paper |
A nearly tight sum-of-squares lower bound for the planted clique problem
SIAM Journal on Computing | 2019-05-07 | Paper |
| Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions | 2019-01-10 | Paper |
Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
(available as arXiv preprint) | 2019-01-10 | Paper |
On the integrality gap of degree-4 sum of squares for planted clique
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Communication with contextual uncertainty
Computational Complexity | 2018-11-07 | Paper |
On the integrality gap of degree-4 sum of squares for planted clique
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Communication with contextual uncertainty
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation) | 2018-07-09 | Paper |
Sum of squares lower bounds for refuting any CSP
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | 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 |
| Embedding hard learning problems into Gaussian space | 2017-03-22 | Paper |
Agnostic learning of disjunctions on symmetric distributions
Journal of Machine Learning Research (JMLR) | 2016-02-19 | Paper |
Agnostic learning of disjunctions on symmetric distributions
Journal of Machine Learning Research (JMLR) | 2016-02-19 | Paper |
Sum of squares lower bounds from pairwise independence (extended abstract)
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Almost Optimal Pseudorandom Generators for Spherical Caps
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
An explicit VC-theorem for low-degree polynomials
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
(available as arXiv preprint) | N/A | Paper |
