Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander A. Sherstov:

TR18-010 | 14th January 2018
Alexander A. Sherstov

Algorithmic polynomials

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

TR17-184 | 29th November 2017
Vladimir Podolskii, Alexander A. Sherstov

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems $f\colon(\{0,1\}^n)^{k}\to\{0,1\}$ with $k\gg\log n$ parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every $k\geq\log n$, showing in both cases that $\Theta(1+\lceil\log n\rceil/\log\lceil1+k/\log n\rceil)$ bits are ... more >>>

TR17-079 | 1st May 2017
Alexander A. Sherstov, Pei Wu

Optimal Interactive Coding for Insertions, Deletions, and Substitutions

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

TR16-138 | 3rd September 2016
Alexander A. Sherstov

On multiparty communication with large versus unbounded error

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

TR16-081 | 20th May 2016
Alexander A. Sherstov

Compressing interactive communication under product distributions

We study the problem of compressing interactive communication to its
information content $I$, defined as the amount of information that the
participants learn about each other's inputs. We focus on the case when
the participants' inputs are distributed independently and show how to
compress the communication to $O(I\log^{2}I)$ bits, with ... more >>>

TR15-147 | 8th September 2015
Alexander A. Sherstov

The Power of Asymmetry in Constant-Depth Circuits

The threshold degree of a Boolean function $f$ is the minimum degree of
a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced
in the seminal work of Minsky and Papert (1969), this notion is central to
some of the strongest algorithmic and complexity-theoretic results for
more >>>

TR14-009 | 21st January 2014
Alexander A. Sherstov

Breaking the Minsky-Papert Barrier for Constant-Depth Circuits

The threshold degree of a Boolean function $f$ is the minimum degree of
a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969
monograph, Minsky and Papert constructed a polynomial-size constant-depth
$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ... more >>>

TR13-023 | 6th February 2013
Alexander A. Sherstov

Approximating the AND-OR Tree

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial
that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,
known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight
and closes a ... more >>>

TR13-005 | 2nd January 2013
Alexander A. Sherstov

Communication Lower Bounds Using Directional Derivatives

We prove that the set disjointness problem has randomized communication complexity
$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement
on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>>

TR12-037 | 10th April 2012
Alexander A. Sherstov

Making Polynomials Robust to Noise

A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has ... more >>>

TR11-145 | 2nd November 2011
Alexander A. Sherstov

The Multiparty Communication Complexity of Set Disjointness

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

TR11-063 | 19th April 2011
Alexander A. Sherstov

The Communication Complexity of Gap Hamming Distance

In the gap Hamming distance problem, two parties must
determine whether their respective strings $x,y\in\{0,1\}^n$
are at Hamming distance less than $n/2-\sqrt n$ or greater
than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and
Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound
on the randomized communication ... more >>>

TR11-040 | 22nd March 2011
Alexander A. Sherstov

Strong Direct Product Theorems for Quantum Communication and Query Complexity

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

TR10-060 | 5th April 2010
Dmitry Gavinsky, Alexander A. Sherstov

A Separation of NP and coNP in Multiparty Communication Complexity

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic
complexity $O(\log n)$ and Merlin-Arthur
complexity $n^{\Omega(1)}$.
The problem was open for $k\geq3$.

more >>>

TR10-025 | 24th February 2010
Alexander A. Sherstov

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function
$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a
real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We
prove that the intersection of two halfspaces on
$\{0,1\}^n$ has threshold degree $\Omega(n),$ which
matches the trivial upper bound and completely answers
a question due to Klivans (2002). The best ... more >>>

TR09-098 | 9th October 2009
Alexander A. Sherstov

The intersection of two halfspaces has high threshold degree

Revisions: 1

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

TR08-057 | 14th May 2008
Alexander A. Sherstov

Communication Lower Bounds Using Dual Polynomials

Representations of Boolean functions by real polynomials
play an important role in complexity theory. Typically,
one is interested in the least degree of a polynomial
p(x_1,...,x_n) that approximates or sign-represents
a given Boolean function f(x_1,...,x_n). This article
surveys a new and growing body of work in communication
complexity that centers ... more >>>

TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

The Sign-Rank of AC^0

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>

TR07-116 | 25th September 2007
Alexander A. Sherstov

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

Let A_1,...,A_n be events in a probability space. The
approximate inclusion-exclusion problem, due to Linial and
Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given
Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve
this problem optimally for each k. We study the following more
general question: ... more >>>

TR07-112 | 25th September 2007
Alexander A. Sherstov

Unbounded-Error Communication Complexity of Symmetric Functions

The sign-rank of a real matrix M is the least rank
of a matrix R in which every entry has the same sign as the
corresponding entry of M. We determine the sign-rank of every
matrix of the form M=[ D(|x AND y|) ]_{x,y}, where
D:{0,1,...,n}->{-1,+1} is given and ... more >>>

TR07-100 | 25th September 2007
Alexander A. Sherstov

The Pattern Matrix Method for Lower Bounds on Quantum Communication

In a breakthrough result, Razborov (2003) gave optimal
lower bounds on the communication complexity of every function f
of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in
the bounded-error quantum model with and without prior entanglement.
This was proved by the _multidimensional_ discrepancy method. We
give an entirely ... more >>>

TR07-072 | 2nd July 2007
Alexander A. Sherstov

Communication Complexity under Product and Nonproduct Distributions

We solve an open problem of Kushilevitz and Nisan
(1997) in communication complexity. Let $R_{eps}(f)$
and $D^{mu}_{eps}(f)$ denote the randomized and
$mu$-distributional communication complexities of
f, respectively ($eps$ a small constant). Yao's
well-known Minimax Principle states that
R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }.
Kushilevitz and Nisan (1997) ask whether ... more >>>

TR06-057 | 19th April 2006
Adam Klivans, Alexander A. Sherstov

Cryptographic Hardness Results for Learning Intersections of Halfspaces

We give the first representation-independent hardness results for
PAC learning intersections of halfspaces, a central concept class
in computational learning theory. Our hardness results are derived
from two public-key cryptosystems due to Regev, which are based on the
worst-case hardness of well-studied lattice problems. Specifically, we
prove that a polynomial-time ... more >>>

ISSN 1433-8092 | Imprint