DIMACS Theoretical Computer Science Seminar

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


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