Deeper Combinatorial Lower Bounds

Computer Science/Discrete Mathematics Seminar II
Topic:Deeper Combinatorial Lower Bounds
Speaker:Siu Man Chan
Affiliation:Princeton University
Date:Tuesday, January 21
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2014/0121-SiuChan

We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections to boolean complexity, proof complexity, and algebraic complexity.