From the Inside: Lower Bounds in Computational Complexity

by Avi Wigderson (Institute for Advanced Study, Princeton)Ryan Williams (Massachusetts Institute of Technology) and Amir Yehudayoff (Technion Israel Institute of Technology)

Some problems are easy to solve, and some are difficult. Adding two numbers seems easier than multiplying them. Tic-tac-toe is easier than chess. Checking a clever answer to a puzzle is easier than finding that answer.

Why are some problems so much harder to solve than others? Can we find generic reasons why many problems appear difficult to solve, no matter how we try to solve them? Currently, these questions are mostly big mysteries. Many problems may be easy to solve, but we simply have not found a good way to solve them yet!

Computational complexity theory tries to formally answer these and related questions. The starting point is defining coherent models of computation. We need to decide things like:

  • What are the allowed operations our algorithms can perform?
  • When does a computation achieve its goal?
  • What bounded resources (time, memory, communication, etc.) do we want to model?

The seminal model of computation is the Turing Machine, defined by Alan Turing in the 1930s as part of his solution to a fundamental mathematics problem raised by David Hilbert. Today there are many other standard models of computation that correspond to different scenarios.

The Fall 2018 Simons Institute program on Lower Bounds in Computational Complexity focused on computational lower bounds — bounding from below the amount of resources that are required in order to complete a given task. The goals of the program were to find new ways to prove lower bounds on computational complexity, to build theories unifying existing knowledge, and to deepen connections among different areas of computational complexity.

To prove lower bounds, we must develop ways of mathematically reasoning about all resource-bounded algorithms. This makes proving lower bounds a challenging task. Furthermore, there are formal "barriers", no-go theorems showing that most known methods for proving lower bounds are severely limited. One focus of our semester was to creatively attack these barriers.

The challenge is often worth the effort. There are intriguing connections between algorithm design and lower bounds. Algorithms can be used to prove lower bounds, and lower bounds can be used to design algorithms!

The semester began with a boot-camp week of expository talks by experts from a wide variety of areas; the resulting videos are a fantastic source of introductory material. 

Our weekly seminars were organized by Rafael Mendes De Oliveira and Avishay Tal. We learned about recent results on diverse topics. Talks were given by long-term participants, short-term visitors, and other guests.

We held four weekly reading groups. Or Meir organized a group on the KRW conjecture — an approach for proving lower bounds by studying the composition of functions. Christian Ikenmeyer organized a group on algebraic complexity theory — the study of the computational complexity of polynomials. Yuval Filmus organized a group on lifting — a framework for reducing lower bounds on "complex" models to lower bounds on "simple" ones. And Marco Carmosino organized a group on the minimum circuit-size problem — the problem of finding the smallest boolean circuit computing a given function.

Faith Ellen organized a couple of interesting meetings with the visiting journalist Anil Ananthaswamy, about how to make lower bounds accessible to the public.

The themes of the program’s workshops followed a natural partition to computational models. The first workshop focused on the boolean world, reporting on new developments in boolean circuit complexity, proof complexity, and related topics. The second workshop focused on interactive models of communication, such as data structures, streaming algorithms, and communication complexity. The focus of the third workshop was algebraic models of computation, such as algebraic circuits and formulas, polynomial identity testing, and so on.

Throughout the semester, we enjoyed many other scientific and social activities. We shared the amazing public space offered by the Simons Institute, and met daily for cookies, tea and coffee. There were game nights, music nights, trivia nights, and pub nights.

Related Articles

,