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.
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
This is related to lower bounds in propositional logic and independence
results in bounded arithmetic.