Andrej Bogdanov 
IAS

TITLE: Worst-case versus average-case hardness for NP

ABSTRACT:

The gold standard of difficulty for a computational problem is NP
hardness. The security of most cryptographic tasks, on the other hand,
is based on assumptions that are seemingly stronger than P != NP.
Intuitively, we expect solving satisfiability to be harder than
breaking encryption because a solver for satisfiability must work on
all formulas, while an adversary for encryption need only succeed on a
random ciphertext. The hardness of satisfiability is based on a
worst-case hardness assumption (namely P != NP), while most of
cryptography appears to require average case hardness assumptions.

However, the intriguing possibility that cryptography and much of 
average-case complexity can be based on NP hardness remains open. 
Certain constructions in cryptography and coding theory suggest that 
such a connection may be possible. In this talk I will discuss 
contrasting evidence that partially explains why a connection between 
worst-case and average-case hardness for NP is difficult to establish.

Joint work with Luca Trevisan (Berkeley)