### 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

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