Stack Exchange

Stattrav

Bangalore, India

http://suryajith.in

a lazy dude!

top accounts reputation activity subscriptions

Top Questions

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis asked Sep 28, 2012 at 11:47

cstheory.stackexchange.com

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis asked Sep 20, 2012 at 9:06

cstheory.stackexchange.com

Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]?

circuit-complexity arithmetic-circuits asked Feb 19, 2013 at 17:49

cstheory.stackexchange.com

Top Answers

No answers with score of 5 or more