Parity helps to compute majority

Christian Engels September 06, 2019

Resources

[https://eccc.weizmann.ac.il/report/2019/073/download](Oliveira, Santhanam, Srinivasan)

Theorem 1: Let $d>5$, Majority on $n$ bits can be computed by a depth-$d$ $AC^0[\oplus]$ circuit of size $2^{\tilde O(n^{2/3 \frac 1 {d-4}})}$.
Theorem 2: For any $d\geq 3$ Majority requires $AC^0[\oplus]$ circuits of depth-$d$ and $2^{\tilde O(n^{\frac 1 {2d-4}})}$ size.
The upper bound is stronger than known $AC_0$ (without parity) lower bounds, meaning parity helps compute majority.

For inputs of hamming distance $t$ of $n/2$ use a $t$-degree polynomial to compute majority. It is symmetric and over $\mathbb{F}_2$ and can be represented as a circuit of size $\exp(t^{2/d} \log n)$.
When the weight is $t$ far from $n/2$ use sampling and Coin Problem to get size $\exp((n/t)^{1/d})$, both of depth $d$.

General idea: any such circuit can be approximated by low degree polynomials and composing these approximations together. Then show that majority does not have low degree polynomial approximation.
They improve the best known bound for this technique in the following way:
- The standard approximation is one-sided, meaning that the approximation is much better on $C^{-1}(0)$ versus $C^{-1}(1)$.
- Hence, they need to show that any polynomial that approximates correctly an $\epsilon$ fraction of the 0-inputs but may error on a constant fraction of the 1-inputs.
- The last part uses the combinatorics on hilbert functions.

Notice that every symmetric boolean function just looks at the weight of the assignment
Then we just need to be able to compute the function that is one on weight $i$ and zero on every other weight ($E_i$) as $f$ can be written as a disjunction of $n+1$ different $E_i$ for different $i$.
Then we can $D_{i,j}$ that is 1 on hamming weight $i$ and 0 on hamming weight $j$ as $E_i=\wedge_{0\leq j\leq n, i\neq j} D_{i,j}$.
Hence, computing $D_{i,j}$ with $AC_0[\oplus]$ is enough.
Now the proof splits into parts

There exists integers $c_1,\dots, c_{l-1}$ and a polynomial of degree at most $l-1$ and integer coefficients such that for all $x$, $x$ has hamming weight $k+t$, $p(x)=c_t$
This polynomial can be constructed by a sum over elementary symmetric polynomials.
Since parity of an integer is a ring homomorphism we can use the above lemma to compute $D_{i,j}$
Now as this can be computed by a ABP, we can divide and conquer this ABP to construct a circuit with the top gate being a parity gate.
This gives us: $AC_0[\oplus]$ circuit of size $n^{O(\lvert i - j\rvert^{2/d'} )}$ and depth $d'$.

Let $Prom_{a,b}$ be the function that is 0 if the hamming weight is smaller than $a$ and 1 if the hamming weight is larger than $b$.
$D_{i,j}$ can be given by $\Prom_{a,b}$ for with some padding of the input.
This can now be computed by a randomized $AC_0$ circuit and this construction can be derandomized.
Resulting in a circuit of the size: $\exp(O(n/\lvert i - j \rvert )^{1/(d'-2)})$.

We call a probabilistic $(\epsilon_1, \epsilon_b)$-error polynomial for a boolean function $f$ if the probability that $P(a)$ differs from $f(a)$ on $a\in f^{-1}(b)$ is bounded by $e_b$ for a bit $b\in {0,1 }$.
Here $P$ is chosen from a distribution.
By the Razborov construction we get polynomials that approximate the boolean function
For the output gate, we construct instead a $(0,1/20)$-error probabilistic polynomial. Again this comes from the Razborov construction.

All polynomials that have error characteristic $1/10,\epsilon$ or $\epsilon,1/10$ have degree at least $\sqrt{n\log (1/\epsilon)}$.
A non-zero certifying polynomial $R$ for a boolean function $f$, if $f$ is constant on the support of $f$.
If $R$ is a certifying polynomial for Majority then $\deg(R) \geq \lceil n/2 \rceil$.
There is a non-zero degree polynomial $Q$ of low degree such that vanishes on all points in $E_0 = { x\in Maj^{-1}(0)\mid P(x)\neq 0}$.
Let $P$ be the polynomial approximating Majority.
Look at now $R=P\cdot Q$. If this is non-zero then it is a certifying polynomial for majority.
Indeed we can find an $a\in supp(P)$ such that $Q(a)\neq 0$.
Theorem: Fix any $E\subseteq \mathbb{F}_2^n$$ then $\frac{\lvert a\mid Q(a)=0 \forall Q \text{of degree at most $D$ that vanish on $E$}}{2^n} \leq \frac{\lvert E\rvert}{N_D}$ where $N_D$ is the number of multilinear monomials of degree $D$.
Intuitively this says that if $E$ is chosen not too large then constraining a polynomial of degree $D$ to be zero on $E$ does not restrict it too much.

Dealing with constant depth circuit, why not have the other gates be similarly "skew". With the constant depth, the error shouldn't be too large?
- This would not give a better bound as the degree lower bound already is independent of where the one-sidedness occurs.