
Statistical Query Algorithms and LowDegree Tests Are Almost Equivalent
Researchers currently use a number of approaches to predict and substant...
read it

Computational Barriers to Estimation from LowDegree Polynomials
One fundamental goal of highdimensional statistics is to detect or reco...
read it

Playing Unique Games on Certified SmallSet Expanders
We give an algorithm for solving unique games (UG) instances whose const...
read it

Subexponential LPs Approximate MaxCut
We show that for every ε > 0, the degreen^ε SheraliAdams linear progra...
read it

SheraliAdams Strikes Back
Let G be any nvertex graph whose random walk matrix has its nontrivial ...
read it

SOS lower bounds with hard constraints: think global, act local
Many previous SumofSquares (SOS) lower bounds for CSPs had two deficie...
read it

Highdimensional estimation via sumofsquares proofs
Estimation is the computational task of recovering a hidden parameter x ...
read it

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
We give a quasipolynomial time algorithm for the graph matching problem ...
read it

The threshold for SDPrefutation of random regular NAE3SAT
Unlike its cousin 3SAT, the NAE3SAT (notallequal3SAT) problem has th...
read it

Computing exact minimum cuts without knowing the graph
We give queryefficient algorithms for the global mincut and the st cu...
read it

The power of sumofsquares for detecting hidden structures
We study planted problemsfinding hidden structures in random noisy in...
read it

Fast and robust tensor decomposition with applications to dictionary learning
We develop fast spectral algorithms for tensor decomposition that match ...
read it

Fast spectral algorithms from sumofsquares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: th...
read it

Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube
We give an algorithm for completing an orderm symmetric lowrank tensor...
read it
Tselil Schramm
is this you? claim profile