Speaker: Prof.Albert Atserias Universitat Politenica de Catalunya, Barcelona
Time: 2014-07-07 13:30-2014-07-07 14:30
Venue: FIT 1-222

Abstract:

I will start this talk by giving an overview of the status of the weak pigeonhole principle (WPHP) in proof complexity and the connection between this problem and some fundamental questions on the computational complexity of approximate counting. Then I will discuss some recent progress on the main remaining question about WPHP, namely whether the known quasipolynomial-size depth-2 proof is optimal in terms of size. We show that a relativized version of the WPHP that also has quasipolynomial-size depth-2 proofs does indeed require quasipolynomial size to prove in depth-2. To our knowledge, this gives the first example of a natural principle with matching but superpolynomial upper and lower bounds in a natural proof system.

Short Bio:

Albert Atserias is an Associate Professor at Universitat Politenica de Catalunya, Barcelona. He received an engineering degree in computer science in 1997 from the Universitat Politenica de Catalunya, an M.Sc. in computer science from the University of California at Santa Cruz (UCSC) in 1999, a Ph.D. in computer science from UPC in 2002, and a Ph.D. in computer science from UCSC also in 2002. In 2008, Dr. Atserias was a visiting scholar at the EECS department of the University of California at Berkeley.
 
Atserias' research interests are in computational complexity, combinatorics, and applications of logic to computer science. More specifically, he has contributed to propositional proof complexity, descriptive complexity, and finite model theory. Dr. Atserias' work is known for building bridges between the two traditional tracks of theoretical computer science (track A and track B). Among his best known achievements is the connection he established between the two-player games for inexpressibility results in finite model theory and lower bound methods for propositional proof systems in proof complexity. In 2002 he received the Kleene Award for best student paper at the LICS conference for pioneering work in this area. More recent work of 2012 further connects the two-player games with lift-and-project methods in mathematical programming.