Complexity Theory

Date: 23 - 26 July 2018

Location: Mathematical Institute, University of Oxford

This workshop will focus on a unifying theme in recent research on complexity theory, informally termed “meta-complexity.”  Meta-complexity refers to the computational complexity of problems whose instances themselves encode algorithms or computations. Some of the fundamental questions in theoretical computer science are questions about meta-complexity, including:  Is the Satisfiability Problem solvable in less than exponential time?  Do pseudo-random generators exist?  Is efficient learning of concepts feasible?  Are complexity lower bounds provable in standard proof systems?

These questions connect complexity theory to a wide range of other areas, including algorithms, learning, cryptography, and logic.  This workshop will build on these connections by stimulating cross-disciplinary conversations between researchers and students working in these areas, with the aim of achieving a deeper and more integrated mathematical understanding of computation.

Speakers:  Josh Alman (MIT), Marco Carmosino (UC San Diego), Ardakev Chattopadhyay (TIFR), Lance Fortnow (GaTech), Joshua Grochow (CU Boulder), Yuval Ishai (Technion), Valentine Kabanets (Simon Fraser), Daniel Kane (UC San Diego), Neeraj Kayal (Microsoft), Antonina Kolokolova (Memorial Newfoundland), Michal Koucký (Charles), Jan Krajicek (Charles), Andrea Lincoln (MIT), Ryan O’Donnell (Carnegie Mellon), Igor Oliveira (Oxford), Toniann Pitassi (Toronto), Pavel Pudlak (CAS), Alexander Razborov (Chicago), Ben Rossman (Toronto), Srikanth Srinivasan (IIT Bombay), Avishay Tal (Stanford), Ryan Williams (MIT), Virginia Vassilevska Williams (MIT)