Alexander A. Sherstov

The threshold degree of a Boolean function

$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real

polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We

construct two halfspaces on $\{0,1\}^n$ whose intersection has

threshold degree $\Theta(\sqrt n),$ an exponential improvement on

previous lower bounds. This solves an open problem due to Klivans

(2002) and ...
more >>>

Russell Impagliazzo, Valentine Kabanets

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,

our proof does not use the method of higher moments, but rather uses a simple ...
more >>>

Andrew Drucker

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.

We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm

has success probability at ...
more >>>

Alexander A. Sherstov

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic

communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$

These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties

were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ...
more >>>

Oded Goldreich

We consider three types of multiple input problems in the context of property testing.

Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:

Given a sequence of $m$ inputs, output a sequence ...
more >>>