All reports by Author Alexander A. Sherstov:

__
TR22-123
| 4th September 2022
__

Alexander A. Sherstov#### The Approximate Degree of DNF and CNF Formulas

__
TR20-128
| 3rd September 2020
__

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu#### An Optimal Separation of Randomized and Quantum Query Complexity

Revisions: 1

__
TR19-121
| 17th September 2019
__

Alexander A. Sherstov, Justin Thaler#### Vanishing-Error Approximate Degree and QMA Complexity

__
TR19-016
| 5th February 2019
__

Alexander A. Sherstov#### The hardest halfspace

__
TR19-003
| 2nd January 2019
__

Alexander A. Sherstov, Pei Wu#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

__
TR18-010
| 14th January 2018
__

Alexander A. Sherstov#### Algorithmic polynomials

__
TR17-184
| 29th November 2017
__

Vladimir Podolskii, Alexander A. Sherstov#### Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

__
TR17-079
| 1st May 2017
__

Alexander A. Sherstov, Pei Wu#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

__
TR16-138
| 3rd September 2016
__

Alexander A. Sherstov#### On multiparty communication with large versus unbounded error

__
TR16-081
| 20th May 2016
__

Alexander A. Sherstov#### Compressing interactive communication under product distributions

__
TR15-147
| 8th September 2015
__

Alexander A. Sherstov#### The Power of Asymmetry in Constant-Depth Circuits

__
TR14-009
| 21st January 2014
__

Alexander A. Sherstov#### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits

__
TR13-023
| 6th February 2013
__

Alexander A. Sherstov#### Approximating the AND-OR Tree

__
TR13-005
| 2nd January 2013
__

Alexander A. Sherstov#### Communication Lower Bounds Using Directional Derivatives

__
TR12-037
| 10th April 2012
__

Alexander A. Sherstov#### Making Polynomials Robust to Noise

__
TR11-145
| 2nd November 2011
__

Alexander A. Sherstov#### The Multiparty Communication Complexity of Set Disjointness

__
TR11-063
| 19th April 2011
__

Alexander A. Sherstov#### The Communication Complexity of Gap Hamming Distance

__
TR11-040
| 22nd March 2011
__

Alexander A. Sherstov#### Strong Direct Product Theorems for Quantum Communication and Query Complexity

__
TR10-060
| 5th April 2010
__

Dmytro Gavinsky, Alexander A. Sherstov#### A Separation of NP and coNP in Multiparty Communication Complexity

__
TR10-025
| 24th February 2010
__

Alexander A. Sherstov#### Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

__
TR09-098
| 9th October 2009
__

Alexander A. Sherstov#### The intersection of two halfspaces has high threshold degree

Revisions: 1

__
TR08-057
| 14th May 2008
__

Alexander A. Sherstov#### Communication Lower Bounds Using Dual Polynomials

__
TR08-016
| 26th February 2008
__

Alexander Razborov, Alexander A. Sherstov#### The Sign-Rank of AC^0

__
TR07-116
| 25th September 2007
__

Alexander A. Sherstov#### Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

__
TR07-112
| 25th September 2007
__

Alexander A. Sherstov#### Unbounded-Error Communication Complexity of Symmetric Functions

__
TR07-100
| 25th September 2007
__

Alexander A. Sherstov#### The Pattern Matrix Method for Lower Bounds on Quantum Communication

__
TR07-072
| 2nd July 2007
__

Alexander A. Sherstov#### Communication Complexity under Product and Nonproduct Distributions

__
TR06-057
| 19th April 2006
__

Adam Klivans, Alexander A. Sherstov#### Cryptographic Hardness Results for Learning Intersections of Halfspaces

Alexander A. Sherstov

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This ... more >>>

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>

Alexander A. Sherstov, Justin Thaler

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

Alexander A. Sherstov

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>>

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

Alexander A. Sherstov

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

Vladimir Podolskii, Alexander A. Sherstov

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

Alexander A. Sherstov, Pei Wu

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Dmytro Gavinsky, Alexander A. Sherstov

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

Alexander A. Sherstov

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

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

Alexander A. Sherstov

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

Alexander Razborov, Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Alexander A. Sherstov

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

Adam Klivans, Alexander A. Sherstov

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