Connections Between Algorithm Design and Complexity Theory
Organizers:
Much significant work on lower bounds in complexity theory has arisen from reconsidering the basic lower bound problem in an algorithmic light. Namely, if computations on small circuits can be performed somewhat efficiently, then this strongly suggests limitations on what tasks can be done with small circuits. Formalizing this intuition has led to generic connections between nontrivial algorithms which perform interesting computations on given circuit classes, and nontrivial complexity limitations on the same circuit classes. This workshop aims to bring many algorithm designers and complexity theorists together to discuss the developments in their respective areas and to reconsider these connections broadly.
All talks will be recorded. Enquiries may be sent to the organizers workshop_complexity1 [at] lists.simons.berkeley.edu (at this address.)
Support is gratefully acknowledged from:
Visit the schedule page for the live-stream and archived videos.
Dimitris Achlioptas (UC Santa Cruz), Eric Allender (Rutgers University), Nikhil Bansal (Technische Universiteit Eindhoven), Boaz Barak (Microsoft Research New England), Paul Beame (University of Washington), Manuel Blum (Carnegie Mellon University), Karl Bringmann (ETH Zürich), Sam Buss (UC San Diego), Marco Carmosino (UC San Diego), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Ruiwen Chen (Simon Fraser University), Radu Curticapean (Universität des Saarlandes), Holger Dell (Universität des Saarlandes), Fedor Fomin (University of Bergen), Michael Forbes (Massachusetts Institute of Technology), Lance Fortnow (Georgia Institute of Technology), Nicola Galesi (Sapienza University Rome), Jiawei Gao (UC San Diego), Parikshit Gopalan (Microsoft Corporation), Monika Henzinger (University of Vienna), Thore Husfeldt (IT University of Copenhagen), Russell Impagliazzo (UC San Diego), Bart Jansen (Eindhoven University of Technology), Valentine Kabanets (Simon Fraser University), Marek Karpinski (University of Bonn), Petteri Kaski (Aalto University), Eunjung Kim (CNRS / Paris Dauphine University), Pascal Koiran (École Normale Supérieure de Lyon), Antonina Kolokolova (Memorial University of Newfoundland), Sebastian Krinninger (University of Vienna), Alexander Kulikov (St. Petersburg Department of Steklov Institute of Mathematics), Richard Lipton (Georgia Institute of Technology), Dániel Marx (Hungarian Academy of Sciences), Raghu Meka (UCLA), Ivan Mikhailin (UC San Diego), Jesper Nederlof (Eindhoven University of Technology), Igor Oliveira (Columbia University), Ramamohan Paturi (UC San Diego), Marcin Pilipczuk (University of Warsaw), Toniann Pitassi (University of Toronto), Aaron Potechin (Massachusetts Institute of Technology), Pavel Pudlák (Academy of Sciences of the Czech Republic), Omer Reingold (Weizmann Institute), Steven Rudich (Carnegie Mellon University), Barna Saha (University of Massachusetts Amherst), Rahul Santhanam (University of Edinburgh), Stefan Schneider (UC San Diego), Ronen Shaltiel (University of Haifa), Srikanth Srinivasan (Indian Institute of Technology Bombay), Suguru Tamaki (Kyoto University), Robert Tarjan (Princeton University), Chris Umans (California Institute of Technology), Avi Wigderson (IAS, Princeton), Virginia Vassilevska Williams (Stanford University), Emanuele Viola (Northeastern University), Magnus Wahlström (Royal Holloway, University of London), Ryan Williams (Stanford University), David Zuckerman (University of Texas, Austin).
