Winter, 2014

** Students should consult this page at least once a week
for important information. **

** **Posted Jan 6** See link below for choosing your topic for a research presentation. Your topic choice is due by Jan 20. **

** Lectures: ** Wednesday 12-2 BA B026

** Instructor: ** Toniann Pitassi

Office: Sandford Fleming 2305A, 978-3695

Office Hours: by appointment

** RESEARCH PRESENTATION **

** OUTLINE AND LECTURE NOTES **

Introduction. The random restriction method. Superpolynomial lower bounds for Resolution proofs of PHP.

Hastad's Switching Lemma, exponential lower bounds for AC0 circuits for parity, and lower bounds on correlation.

Applications of AC0 lower bounds: Fourier concentration for AC0 and PAC learning of AC0 (over uniform distribution), Pseudorandom generators for AC0, AC0-SAT algorithm, Compression algorithm for AC0, Compression games for AC0, Bounded-depth Frege lower bounds.

Formula size lower bounds, and average-case formula size lower bounds.

Communication Complexity approaches to Circuit Lower Bounds.

(Guest Speaker: Stephen Cook) The Tree Evaluation Problem and Towards Separating P from NL.

(Guest Speaker: Josh Grochow) Algebraic circuit complexity. Lower Bounds via connected components. Intro to Mulmuley's lower bound in Algebraic PRAM model without bit operations.

(Guest Speaker: Josh Grochow) Continuation of Mulmuley's lower bound.

(Guest Speaker: Josh Grochow)

(Guest Speaker: Mika Goos) Matrix Rigidity and Communication Complexity.

(Guest Speaker: Robert Robere) ACC is not in NEXP (Ryan Williams' result)

(Guest Speaker: David Liu) Barriers: Natural Proofs and Algebrization