Some Recent Papers

(Click here for all papers)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
Metastable Mixing of Markov Chains: Efficiently Sampling Low Temperature Exponential Random Graphs
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Best Paper Runner Up
Reducibility and Statistical-Computational Gaps from Secret Leakage
Best Student Paper Award
Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
Phase Transitions for Detecting Latent Geometry in Random Graphs
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs

Contact

  • guy@mit.edu
  • (617) 324-1549
  • 32-D672, 32 Vassar St., Cambridge, MA 02139