Presented by:
A Atserias [Politecnica de Catalunya]
Date:
Monday 6th February 2006 - 11:00 to 12:00
Venue:
INI Seminar Room 1
Event:
Abstract:
We may believe SAT does not have small Boolean circuits. But is it possible that some language with small circuits looks indistiguishable from SAT to every polynomial-time bounded adversary? We rule out this possibility. More precisely, assuming SAT does not have small circuits, we show that for every language $A$ with small circuits, there exists a probabilistic polynomial-time algorithm that makes black-box queries to $A$, and produces, for a given input length, a Boolean formula on which $A$ differs from SAT. This will be a blackboard lecture (no slides).