Abstract
Celebrated Rice's theorem in computability theory states that any non-trivial semantic property of Turing machines is undecidable. That is, to check if the language accepted by a Turing machine satisfies some property, essentially the only thing one can do is to run the machine.
Is there is a similar phenomenon in the complexity theory world? Following a conjecture posed by Barak et al. in their paper on impossibility of obfuscation, we ask whether working with a description of a Boolean circuit gives any computational advantage for deciding properties of a Boolean function, as opposed to a black-box (oracle) access.
We show that for read-once branching programs there is indeed such an advantage. For general Boolean circuits, we make a step towards resolving this question by showing that if properties of a certain type are easier to decide given a circuit description then there is a non-trivial algorithm for the CircuitSAT problem.
Joint work with Russell Impagliazzo, Valentine Kabanets, Pierre McKenzie and Shadab Romani.