Jan Krajicek

Academy of Sciences of the Czech Republic

Effective Interpolation Theorems, Cryptographical Conjectures, and Hard Tautologies.

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

April 12, 2:30 p.m.

Abstract:

I shall discuss a consequence of a cryptographical conjecture about the existence of one-way functions for effective interpolation theorems (those theorems give bounds to the complexity of an interpolant of an implication in terms of the size of a proof of the implication).

This is related to lower bounds in propositional logic and independence results in bounded arithmetic.