Title: On the Complexity of Circuit Satisfiability
Speaker: Ramamohan Paturi, UCSD
Date: Wednesday, April 22, 2009 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We present a gap theorem regarding the complexity of the circuit satisfiability problem. We prove that the success probability of deciding Circuit Satisfiability for deterministic circuits with $n$ variables and size $m$ is either $2^{-n}$ or $2^{-o(n)$ when restricted to probabilistic circuit families $\{C_{n,m}\}$ where the size of $C_{n,m}$ is bounded by $2^{o(n)}poly(m)$.
Joint work with Pavel Pudlak