Theory of Computing Seminar

Thursday February 4, 2016 3:00 PM

Does looking inside the circuit help?

Speaker: Antonina Kolokolova, Memorial University of Newfoundland
Location: Annenberg 107

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 SAT problem. 
 
Joint work with Russell Impagliazzo, Valentine Kabanets, Pierre McKenzie and Shadab Romani. 

 

Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu