Title: On the Complexity of Circuit Satisfiability

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