Does Looking Inside a Circuit Help?
summary
Asks whether a circuit description gives more power than oracle queries and proves a concrete reduction: if a property of Boolean functions is decidable in BPP given a circuit and the property has an easy sensitive instance (a small-circuit truth table with ≥2^{δn} sensitive bits), then Circuit-SAT admits a nonuniform subexponential-time algorithm. Proof builds an algorithm that XORs the SAT instance with an advice circuit, applies randomized permutation to hit a sensitive bit, and amplifies success with Paturi–Pudlák style amplification; the reduction is explicit and constructive.
AI-written summary · about