All reports by Author Boaz Barak:

__
TR18-077
| 23rd April 2018
__

Boaz Barak, Pravesh Kothari, David Steurer#### Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

__
TR17-065
| 20th April 2017
__

Boaz Barak#### The Complexity of Public-Key Cryptograph

__
TR17-060
| 9th April 2017
__

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari#### Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

__
TR17-011
| 22nd January 2017
__

Boaz Barak, Pravesh Kothari, David Steurer#### Quantum entanglement, sum of squares, and the log rank conjecture

__
TR16-058
| 12th April 2016
__

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin#### A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

__
TR15-082
| 13th May 2015
__

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright#### Beating the random assignment on constraint satisfaction problems of bounded degree

__
TR14-059
| 21st April 2014
__

Boaz Barak, David Steurer#### Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

__
TR13-184
| 23rd December 2013
__

Boaz Barak, Jonathan Kelner, David Steurer#### Rounding Sum-of-Squares Relaxations

__
TR13-182
| 20th December 2013
__

Boaz Barak#### Structure vs Combinatorics in Computational Complexity

__
TR12-120
| 24th September 2012
__

Boaz Barak#### Proof vs. Truth in Computational Complexity

Revisions: 1

__
TR11-142
| 2nd November 2011
__

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer#### Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

__
TR11-065
| 25th April 2011
__

Boaz Barak, Prasad Raghavendra, David Steurer#### Rounding Semidefinite Programming Hierarchies via Global Correlation

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR10-037
| 8th March 2010
__

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

__
TR09-129
| 30th November 2009
__

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR05-114
| 9th October 2005
__

Boaz Barak, Shien Jin Ong, Salil Vadhan#### Derandomization in Cryptography

__
TR05-096
| 26th August 2005
__

Boaz Barak, Amit Sahai#### How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation

__
TR04-083
| 8th September 2004
__

Boaz Barak, Yehuda Lindell, Salil Vadhan#### Lower Bounds for Non-Black-Box Zero Knowledge

__
TR02-026
| 7th April 2002
__

Boaz Barak, Yehuda Lindell#### Strict Polynomial-time in Simulation and Extraction

Revisions: 2

__
TR01-093
| 2nd December 2001
__

Boaz Barak, Oded Goldreich#### Universal Arguments and their Applications

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

Boaz Barak, Pravesh Kothari, David Steurer

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain ``Grassmanian agreement tester''.

In this work, we show that the hypothesis of Dinur et al follows from a ...
more >>>

Boaz Barak

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This is a survey that appeared in a book of surveys in honor of ... more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

Boaz Barak, Pravesh Kothari, David Steurer

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.

This yields a nearly tight ...
more >>>

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

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 (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>>

Boaz Barak, Jonathan Kelner, David Steurer

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

Boaz Barak

Some computational problems seem to have a certain "structure" that is manifested in non-trivial algorithmic properties, while others are more "unstructured" in the sense that they are either "very easy" or "very hard". I survey some of the known results and open questions about this classification and its connections to ... more >>>

Boaz Barak

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer

The long code is a central tool in hardness of approximation, especially in

questions related to the unique games conjecture. We construct a new code that

is exponentially more ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Boaz Barak, Prasad Raghavendra, David Steurer

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with ... more >>>

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

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 least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

more >>>

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

Boaz Barak, Shien Jin Ong, Salil Vadhan

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

Boaz Barak, Amit Sahai

We construct a secure protocol for any multi-party functionality

that remains secure (under a relaxed definition of security) when

executed concurrently with multiple copies of itself and other

protocols. We stress that we do *not* use any assumptions on

existence of trusted parties, common reference string, honest

majority or synchronicity ...
more >>>

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

<ol>

<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ...
more >>>

Boaz Barak, Yehuda Lindell

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>

Boaz Barak, Oded Goldreich

We put forward a new type of

computationally-sound proof systems, called universal-arguments,

which are related but different from both CS-proofs (as defined

by Micali) and arguments (as defined by Brassard, Chaum and

Crepeau). In particular, we adopt the instance-based

prover-efficiency paradigm of CS-proofs, but follow the

computational-soundness condition of ...
more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>