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.