97 citations · 103 across the 4 of their papers we have counts for
4 papers
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari
We prove that for every and predicate that supports a pairwise independent distribution, there exists an instance of the $\math…
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak, Jonathan A. Kelner, David Steurer
We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown matrix (for ) from examples of the form…
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak, David Steurer
In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture…
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
Boaz Barak, Zeev Dvir, Avi Wigderson +1
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at leas…