Parity helps to compute majority
Christian Engels September 06, 2019Resources
- [https://eccc.weizmann.ac.il/report/2019/073/download](Oliveira, Santhanam, Srinivasan)
Results
- Theorem 1: Let , Majority on bits can be computed by a depth- circuit of size .
- Theorem 2: For any Majority requires circuits of depth- and size.
- The upper bound is stronger than known (without parity) lower bounds, meaning parity helps compute majority.
Proof Ideas
Upper Bound
- For inputs of hamming distance of use a -degree polynomial to compute majority. It is symmetric and over and can be represented as a circuit of size .
- When the weight is far from use sampling and Coin Problem to get size , both of depth .
Lower Bound
- 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 versus .
- Hence, they need to show that any polynomial that approximates correctly an 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.
Proof of Upper Bound
- 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 and zero on every other weight () as can be written as a disjunction of different for different .
- Then we can that is 1 on hamming weight and 0 on hamming weight as .
- Hence, computing with is enough.
- Now the proof splits into parts
\lvert i - j \rvert \leq n^
- There exists integers and a polynomial of degree at most and integer coefficients such that for all , has hamming weight ,
- 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
- 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: circuit of size and depth .
- Let be the function that is 0 if the hamming weight is smaller than and 1 if the hamming weight is larger than .
- can be given by for with some padding of the input.
- This can now be computed by a randomized circuit and this construction can be derandomized.
- Resulting in a circuit of the size: .
Linear Threshold function for combining these two
- Any treshold function can be comp0uted by a polynomial size circuit
- This works via standard chinese remainder construction
Proof of Lower Bound
- We call a probabilistic -error polynomial for a boolean function if the probability that differs from on is bounded by for a bit .
- Here 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 -error probabilistic polynomial. Again this comes from the Razborov construction.
Lower bound
- All polynomials that have error characteristic or have degree at least .
- A non-zero certifying polynomial for a boolean function , if is constant on the support of .
- If is a certifying polynomial for Majority then .
- There is a non-zero degree polynomial of low degree such that vanishes on all points in .
- Let be the polynomial approximating Majority.
- Look at now . If this is non-zero then it is a certifying polynomial for majority.
- Indeed we can find an such that .
- Theorem: Fix any \frac{\lvert a\mid Q(a)=0 \forall Q \text{of degree at most that vanish on }}{2^n} \leq \frac{\lvert E\rvert}{N_D}N_DD$.
- Intuitively this says that if is chosen not too large then constraining a polynomial of degree to be zero on does not restrict it too much.
Questions
- 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.