Syllabus for J. Krajicek's lectures at the
Fall school(Sept.'01)

Recent topics in propositional proof complexity
and bounded arithmetic, Part 2.



Lectures 1. and 2. Derandomization and pseudo-random generators.

Probabilistic algorithms and an attempt at derandomization. Definitions of pseudo-random generators and one-way functions, and a theorem relating them. An example in AC^0 world.
Nisan-Wigderson construction. Impagliazzo-Wigderson theorem.

Reference
L.Trevisan's lecture notes from IAS Summer School on Computational Complexity, 2000.


Lectures 3. and 4. Towards hard tautologies: Tau formulas.

General construction of tau-formulas and some earlier examples: Tseitin's formulas, consistency statements, prime tautologies, a formula expressing the hardness of boolean functions.
Relation of tau-formulas to definability and provability in bounded arithmetic (disjoint NP pairs, dual pigeonhole principle). Lower bounds and extensions of models of bounded arithmetic.

Reference
J.Krajicek: Tautologies from pseudo-random generators, Bull.Symbolic Logic, 7(2), (2001), pp.197-212.