papers
Publications (19)
math.CO2011
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
Boaz Barak, Zeev Dvir, Avi Wigderson +1
cs.CC2010
Subsampling Mathematical Relaxations and Average-case Complexity
Boaz Barak, Moritz Hardt, Thomas Holenstein +1
cs.LG2016
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak, Ankur Moitra
quant-ph2017
Quantum entanglement, sum of squares, and the log rank conjecture
Boaz Barak, Pravesh Kothari, David Steurer
cs.CC2018
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Boaz Barak, Pravesh K. Kothari, David Steurer
cs.DS2014
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak, David Steurer
cs.DS2019
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
Boaz Barak, Chi-Ning Chou, Zhixian Lei +2
cs.CC2019
Lower Bounds on Signatures from Symmetric Primitives
Boaz Barak, Mohammad Mahmoody
cs.LG2019
SGD on Neural Networks Learns Functions of Increasing Complexity
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris +4
cs.CC2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
cs.DS2014
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak, Jonathan A. Kelner, David Steurer
cs.DS2011
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
cs.CC2014
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3
cs.CC2011
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
cs.CC2015
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari
math.CO2006
A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph
Boaz Barak
cs.DS2013
Rounding Sum-of-Squares Relaxations
Boaz Barak, Jonathan Kelner, David Steurer
cs.CC2015
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
cs.CC2019
Merkle's Key Agreement Protocol is Optimal: An $O(n^2)$ Attack on any Key Agreement from Random Oracles
Boaz Barak, Mohammad Mahmoody