Nisan-Wigderson generators in proof systems with forms of interpolation

Jan Pich

(Charles University in Prague)

Razborov conjectured that certain tautologies based on suitable Nisan-Wigderson generators do not have short proofs in strong propositional proof systems like Extended Frege. We will discuss the conjecture and prove that tautologies from the conjecture are hard for proof systems that admit feasible interpolation.
Monday 17th January 2011, 11:00
Robert Recorde Room
Department of Computer Science