Skip to content

LAA

Seminar

Non-uniform hardness for NP via black-box adversaries

Atserias, A (Politecnica de Catalunya)
Monday 06 February 2006, 11:00-12:00

Seminar Room 1, Newton Institute

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).

Back to top ∧