Parity helps to compute majority

Christian Engels September 06, 2019

Resources

Results

Proof Ideas

Upper Bound

Lower Bound

Proof of Upper Bound

\lvert i - j \rvert \leq n^

ijn1/3\lvert i - j \rvert \geq n^{1/3}

Linear Threshold function for combining these two

Proof of Lower Bound

Lower bound

Questions