Theory of Computing Seminar
Thursday, February 4, 2016
3:00pm to 4:00pmAdd to Cal
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].