Fall 2015

Fine-Grained Complexity and Algorithm Design

Aug. 19Dec. 18, 2015

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction into a quantitative guide as to the exact time required to solve problems. This characterization makes sense for problems within P, distinguishing between, say, problems that require cubic time and those solvable in quadratic time. It may also guide us as to the exact complexity of hard problems, distinguishing, say, between NP-complete problems where exhaustive search is essentially the best possible algorithm, and those that have improved exponential time algorithms. Additionally, fine-grained complexity aims to precisely delineate the difficulty of instances of computational problems, finding parameters of instances that determine how much time algorithms will take on those instances. Such a complexity theory has the potential to become a real guide for algorithm design, identifying precisely what algorithmic performance is obtainable. In addition, fine-grained complexity is intimately linked to progress on traditional issues in computational complexity: in particular, it is essential to recent breakthroughs in circuit lower bounds via new algorithms, and is tightly linked to the question of derandomization of randomized algorithms.

This agenda, while broad and ambitious, is actually within reach! Recent research has made rapid progress on all of these fronts, and in fact the exciting possibilities mentioned above have been proved to be linked together. All of them emerge from studying the exact and parameterized complexities of NP-complete problems. The precise time complexity of Satisfiability and other NP-complete problems is now linked to progress on a variety of fundamental questions in the theory of computation, many in surprising and counter-intuitive ways. These connections include: the exact complexity of basic problems within P such as matrix multiplication, triangle detection and k-Sum; time-size trade-offs for data structures; circuit lower bounds; derandomization; and parameterized algorithms and complexity. Recent research keeps adding to this list, suggesting that there are even more connections yet to be discovered.

We propose to gather researchers from the computational complexity, algorithm design, parameterized algorithms and Sat-heuristic communities to strengthen and utilize these connections between complexity and algorithm design. Our goals are to develop new algorithms, to prove new lower bounds, to understand the exact time complexity of problems both rigorously and quantitatively, and to strengthen and exploit the connections between algorithm design and lower bounds. As a side effect, we expect to see new algorithms for basic problems (often utilizing techniques from lower bounds), as well as new circuit lower bounds (utilizing improved algorithms).


Ramamohan Paturi (UC San Diego; chair), Russell Impagliazzo (UC San Diego), Dániel Marx (Hungarian Academy of Sciences), Ryan Williams (Stanford University), Virginia Vassilevska Williams (Stanford University)

Long-Term Participants (including Organizers):

Dimitris Achlioptas (UC Santa Cruz), Nikhil Bansal (Technische Universiteit Eindhoven), Paul Beame (University of Washington), Andrew Drucker (University of Chicago), Uriel Feige (Weizmann Institute), Fedor Fomin (University of Bergen), Nicola Galesi (Sapienza University of Rome), Fabrizio Grandoni (IDSIA), Johan Håstad (KTH Royal Institute of Technology), Monika Henzinger (University of Vienna), Thore Husfeldt (IT University of Copenhagen), Russell Impagliazzo (UC San Diego), Bart Jansen (Technische Universiteit Eindhoven), Valentine Kabanets (Simon Fraser University), Petteri Kaski (Aalto University), Eun Jung Kim (CNRS, LAMSADE, Paris Dauphine University), Mikko Koivisto (University of Helsinki), Antonina Kolokolova (Memorial University of Newfoundland), Daniel Lokshtanov (University of Bergen), Dániel Marx (Hungarian Academy of Sciences), Raghu Meka (UCLA), Ramamohan Paturi (UC San Diego; chair), Toniann Pitassi (University of Toronto), Pavel Pudlák (Academy of Sciences of the Czech Republic), Rahul Santhanam (University of Oxford), Suguru Tamaki (Kyoto University), Robert Tarjan (Princeton University), Mikkel Thorup (University of Copenhagen), Emanuele Viola (Northeastern University), Ryan Williams (Stanford University), Virginia Vassilevska Williams (Stanford University), Uri Zwick (Tel Aviv University)

Research Fellows:

Karl Bringmann (ETH Zürich; Qualcomm Research Fellow), Radu Curticapean (Saarland University), Holger Dell (Saarland University and Cluster of Excellence, MMCI), Sebastian Krinninger (University of Vienna, Austria), Jesper Nederlof (Eindhoven University of Technology), Marcin Pilipczuk (University of Warsaw), Aaron Potechin (Massachusetts Institute of Technology), Barna Saha (University of Massachusetts, Amherst), Srikanth Srinivasan (Indian Institute of Technology Bombay)

Visiting Graduate Students and Postdocs:

Amir Abboud (Stanford University), Joshua Alman (Stanford University), Greg Bodwin (Stanford University), Marco Carmosino (UC San Diego), Brynmor Chapman (Stanford University), Grace Dinh (UC Berkeley), Jiawei Gao (UC San Diego), Elad Haramaty (Northeastern University), Marvin Künnemann (Max Planck Institute for Informatics), Chin Ho Lee (Northeastern University), Jingcheng Liu (UC Berkeley), Ivan Mikhailin (UC San Diego), Aviad Rubinstein (UC Berkeley), Manuel Sabin (UC Berkeley), Stefan Schneider (UC San Diego), Seeun William Umboh (Technische Universiteit Eindhoven)


Aug. 31Sep. 4, 2015


Ramamohan Paturi (UC San Diego)
Sep. 28Oct. 1, 2015


Valentine Kabanets (Simon Fraser University), Ryan Williams (Stanford University)
Nov. 2Nov. 6, 2015


Thore Husfeldt (IT University of Copenhagen), Dániel Marx (Hungarian Academy of Sciences), Ramamohan Paturi (UC San Diego)
Nov. 30Dec. 3, 2015


Piotr Indyk (Massachusetts Institute of Technology), Virginia Vassilevska Williams (Stanford University)
Dec. 12Dec. 15, 2016


Russell Impagliazzo (UC San Diego), Dániel Marx (Hungarian Academy of Sciences), Ramamohan Paturi (UC San Diego), Ryan Williams (Stanford University), Virginia Vassilevska Williams (Stanford University)

Program image: "Fine-grained Complexity" by Russell Impagliazzo and Spiro Vassilevski. View a high-resolution version of the program image here.