Comment by amirhirsch
6 hours ago
Yes.
There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
6 hours ago
Yes.
There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
This one? https://www.cs.huji.ac.il/~nati/PAPERS/lmn.pdf
https://en.wikipedia.org/wiki/Switching_lemma
That paper is in the wiki refs but Hastad’s original is from 1986