Theory of Computing Seminar

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 SAT problem. 

 

Joint work with Russell Impagliazzo, Valentine Kabanets, Pierre McKenzie and Shadab Romani.