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