Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Boaz Barak:

TR17-065 | 20th April 2017
Boaz Barak

The Complexity of Public-Key Cryptograph

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 >>>

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)

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 >>>

TR17-011 | 22nd January 2017
Boaz Barak, Pravesh Kothari, David Steurer

Quantum entanglement, sum of squares, and the log rank conjecture

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 >>>

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

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 >>>

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

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 >>>

TR14-059 | 21st April 2014
Boaz Barak, David Steurer

Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

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 >>>

TR13-184 | 23rd December 2013
Boaz Barak, Jonathan Kelner, David Steurer

Rounding Sum-of-Squares Relaxations

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 >>>

TR13-182 | 20th December 2013
Boaz Barak

Structure vs Combinatorics in Computational Complexity

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 >>>

TR12-120 | 24th September 2012
Boaz Barak

Proof vs. Truth in Computational Complexity

Revisions: 1

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.

more >>>

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

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 >>>

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

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 >>>

TR09-129 | 30th November 2009
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

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 >>>

TR09-044 | 6th May 2009
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Direct Sums in Randomized Communication Complexity

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


We show that:

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

TR05-114 | 9th October 2005
Boaz Barak, Shien Jin Ong, Salil Vadhan

Derandomization in Cryptography

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 >>>

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

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 >>>

TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

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:
<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 >>>

TR02-026 | 7th April 2002
Boaz Barak, Yehuda Lindell

Strict Polynomial-time in Simulation and Extraction

Revisions: 2

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 >>>

TR01-093 | 2nd December 2001
Boaz Barak, Oded Goldreich

Universal Arguments and their Applications

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint