Andrew Wiles Building
Radcliffe Observatory Quarter
Oxford OX2 6GG
Organizers: Eric Allender (Rutgers), Ben Green (Oxford), Rahul Santhanam (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: Ardakev Chattopadhyay (TIFR), Andrew Drucker (Chicago), Lance Fortnow (GaTech), Joshua Grochow (CU Boulder), Yuval Ishai (Technion), Valentine Kabanets (Simon Fraser), Daniel Kane (UCSD), Neeraj Kayal (Microsoft), Antonina Kolokolova (Newfoundland), Michal Koucký (Charles), Jan Krajicek (Charles), Ryan O'Donnell (Carnegie Mellon), Mohan Paturi (UCSD), Toniann Pitassi (Toronto), Pavel Pudlak (CAS), Alexander Razborov (Chicago), Ben Rossman (Toronto), Srikanth Srinivasan (IIT Bombay), Ryan Williams (MIT), Virginia Vassilevska Williams (MIT)
Registration: Registration for the workshop is free but required; please contact Naomi Kraker to register.