Pravesh Kothari

Jeff Xu

CoRR, October, 2025

Sparsifying Sums of Positive Semidefinite Matrices.

[BibT_eX]

[DOI]

CoRR, August, 2025

The Quasi-Polynomial Low-Degree Conjecture is False.

[BibT_eX]

[DOI]

CoRR, May, 2025

New Spectral Algorithms for Refuting Smoothed k-SAT.

[BibT_eX]

[DOI]

Commun. ACM, March, 2025

Sum-Of-Squares To Approximate Knapsack.

[BibT_eX]

[DOI]

Sherry Sarkar

CoRR, February, 2025

Rounding Large Independent Sets on Expanders.

[BibT_eX]

[DOI]

Mitali Bafna

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Improved Lower Bounds for all Odd-Query Locally Decodable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Overcomplete Tensor Decomposition via Koszul-Young Flattenings.

[BibT_eX]

[DOI]

Ankur Moitra

Alexander S. Wein

CoRR, 2024

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures.

[BibT_eX]

[DOI]

CoRR, 2024

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs.

[BibT_eX]

[DOI]

Aaron Potechin

Jeff Xu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

New SDP Roundings and Certifiable Approximation for Cubic Optimization.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Semirandom Planted Clique and the Restricted Isometry Property.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Efficient Certificates of Anti-Concentration Beyond Gaussians.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.

[BibT_eX]

[DOI]

Andrej Bogdanov

Alon Rosen

Proceedings of the Theory of Cryptography - 21st International Conference, 2023

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity.

[BibT_eX]

[DOI]

Aravind Gollakota

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Algorithms Approaching the Threshold for Semi-random Planted Clique.

[BibT_eX]

[DOI]

Rares-Darius Buhai

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Privately Estimating a Gaussian: Efficient, Robust, and Optimal.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A simple and sharper proof of the hypergraph Moore bound.

[BibT_eX]

[DOI]

Sidhanth Mohanty

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Ellipsoid Fitting up to a Constant.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error.

[BibT_eX]

[DOI]

He Jia

Santosh S. Vempala

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Is Planted Coloring Easier than Planted Clique?

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

The Price of Strategyproofing Peer Assessment.

[BibT_eX]

[DOI]

CoRR, 2022

List-decodable covariance estimation.

[BibT_eX]

[DOI]

Misha Ivkov

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Robustly learning mixtures of k arbitrary Gaussians.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithmic Thresholds for Refuting Random Polynomial Systems.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Strategyproofing Peer Assessment via Partitioning: The Price in Terms of Evaluators' Expertise.

[BibT_eX]

[DOI]

Proceedings of the Tenth AAAI Conference on Human Computation and Crowdsourcing, 2022

Polynomial-Time Power-Sum Decomposition of Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Private Robust Estimation by Stabilizing Convex Relaxations.

[BibT_eX]

[DOI]

Pasin Manurangsi

Ameya Velingker

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally.

[BibT_eX]

[DOI]

Brian Hu Zhang

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2021

Playing unique games on certified small-set expanders.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time.

[BibT_eX]

[DOI]

Ainesh Bakshi

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Strongly refuting all semi-random Boolean CSPs.

[BibT_eX]

[DOI]

Jackson Abascal

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Stress-Free Sum-Of-Squares Lower Bound for Coloring.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

Memory-Sample Lower Bounds for Learning Parity with Noise.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Tight bounds on ℓ1 approximation and learning of self-bounding functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Robustly Learning Mixtures of k Arbitrary Gaussians.

[BibT_eX]

[DOI]

CoRR, 2020

Outlier-Robust Clustering of Non-Spherical Mixtures.

[BibT_eX]

[DOI]

Ainesh Bakshi

CoRR, 2020

List-Decodable Subspace Recovery via Sum-of-Squares.

[BibT_eX]

[DOI]

Ainesh Bakshi

CoRR, 2020

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG.

[BibT_eX]

[DOI]

Sumegha Garg

Ran Raz

Proceedings of the Approximation, 2020

On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes.

[BibT_eX]

[DOI]

Roi Livni

Proceedings of the Algorithmic Learning Theory, 2020

2019

Semialgebraic Proofs and Efficient Algorithm Design.

[BibT_eX]

[DOI]

Noah Fleming

Toniann Pitassi

Found. Trends Theor. Comput. Sci., 2019

Approximation Schemes for a Buyer with Independent Items via Symmetries.

[BibT_eX]

[DOI]

CoRR, 2019

List-decodable Linear Regression.

[BibT_eX]

[DOI]

Sushrut Karmalkar

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

SOS Lower Bounds with Hard Constraints: Think Global, Act Local.

[BibT_eX]

[DOI]

Ryan O'Donnell

Tselil Schramm

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture.

[BibT_eX]

[DOI]

Boaz Barak

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Sum-of-Squares Meets Program Obfuscation, Revisited.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - EUROCRYPT 2019, 2019

The Social Network Effect on Surprise in Elections.

[BibT_eX]

[DOI]

Palash Dey

Swaprava Nath

Proceedings of the ACM India Joint International Conference on Data Science and Management of Data, 2019

2018

Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium.

[BibT_eX]

[DOI]

Ruta Mehta

Electron. Colloquium Comput. Complex., 2018

Surprise in Elections.

[BibT_eX]

[DOI]

Palash Dey

Swaprava Nath

CoRR, 2018

Robust moment estimation and improved clustering via sum of squares.

[BibT_eX]

[DOI]

Jacob Steinhardt

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Sum-of-squares meets nash: lower bounds for finding any equilibrium.

[BibT_eX]

[DOI]

Ruta Mehta

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Improper Learning by Refuting.

[BibT_eX]

[DOI]

Roi Livni

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation).

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29, 2018

Efficient Algorithms for Outlier-Robust Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

An Analysis of the t-SNE Algorithm for Data Visualization.

[BibT_eX]

[DOI]

Sanjeev Arora

Wei Hu

Proceedings of the Conference On Learning Theory, 2018

2017

Outlier-robust moment-estimation via sum-of-squares.

[BibT_eX]

[DOI]

CoRR, 2017

Better Agnostic Clustering Via Relaxed Tensor Norms.

[BibT_eX]

[DOI]

Jacob Steinhardt

CoRR, 2017

Learning by Refuting.

[BibT_eX]

[DOI]

Roi Livni

CoRR, 2017

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs.

[BibT_eX]

[DOI]

Prasad Raghavendra

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Sum of squares lower bounds for refuting any CSP.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Quantum entanglement, sum of squares, and the log rank conjecture.

[BibT_eX]

[DOI]

Boaz Barak

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Agnostic learning of disjunctions on symmetric distributions.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2015

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Ilan Komargodski

Madhu Sudan

Electron. Colloquium Comput. Complex., 2015

SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four.

[BibT_eX]

[DOI]

Samuel B. Hopkins

Aaron Potechin

CoRR, 2015

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Sum of Squares Lower Bounds from Pairwise Independence.

[BibT_eX]

[DOI]

Boaz Barak

Siu On Chan

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Almost Optimal Pseudorandom Generators for Spherical Caps.

[BibT_eX]

[DOI]

CoRR, 2014

Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions.

[BibT_eX]

[DOI]

CoRR, 2014

Testing Surface Area.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Provable Submodular Minimization using Wolfe's Algorithm.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Prateek Jain

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Learning Coverage Functions and Private Release of Marginals.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

Embedding Hard Learning Problems Into Gaussian Space.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Constructing Hard Functions from Learning Algorithms.

[BibT_eX]

[DOI]

Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2013

Learning Coverage Functions

[BibT_eX]

[DOI]

CoRR, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.

[BibT_eX]

[DOI]

Proceedings of the COLT 2013, 2013

Constructing Hard Functions Using Learning Algorithms.

[BibT_eX]

[DOI]

Igor C. Oliveira

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Differentially Private Online Learning.

[BibT_eX]

[DOI]

Prateek Jain

Abhradeep Thakurta

Proceedings of the COLT 2012, 2012

Submodular functions are noise stable.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

An Explicit VC-Theorem for Low-Degree Polynomials.

[BibT_eX]

[DOI]

Eshan Chattopadhyay