skip to main content

Theory of Computing Seminar

Thursday, February 4, 2016
3:00pm to 4:00pm
Add to Cal
Annenberg 107
Does looking inside the circuit help?
Antonina Kolokolova, Memorial University of Newfoundland,


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. 


For more information, please contact Thomas Vidick by email at [email protected].