Workshop Details

The Minimum Circuit Size Problem (MCSP) takes as input the truth-table of a Boolean function f, and asks about the size of the smallest circuit computing f.  MCSP has been the subject of a large amount of research lately.  This talk will survey some of this work and will try to explain why MCSP is attracting so much attention.

Starting with the classic dimension reduction method, researchers developed powerful tools for storing, communicating, and accessing data pieces more efficiently than merely storing/etc the unprocessed data.

These tools, often studied in the area sublinear algorithms (e.g., sketching), are a form of functional compression, where we store just enough about data pieces to be useful for particular tasks. Most importantly, these tools have led to new algorithms with much better computational efficiency.

In many of the simplest examples of dynamic programming, inputs of size n are processed by constructing an n by n matrix, where each entry is obtained by a simple function of a few entries above and to the left. This yields a simple O(n^2) algorithm for such problems. These algorithms naturally arise, for example, in evaluating various distance measures between two strings, such as LCS (longest common subsequence) distance, Edit Distance, Frechet Distance, and Dynamic Time Warping Distance, and the i,j entry of the matrix gives the desired measure between the length i prefix of the first string, and the length j prefix of the second. With few exceptions (such as the Longest Increasing Subsequence (LIS) problem where the quadratic time algorithm has been improved to O(n log(n)), these quadratic time dynamic programming algorithms remain essentially the fastest exact algorithms (except for n^o(1) factor improvements). This phenomenon has been the focus of much recent research in fine grain complexity, and there is a line of work that shows that for many such problems, reducing the running time to O(n^{2-a}) for some a>0 would contradict the Strong Exponential Time Hypothesis. This suggests that it will be difficult, if not impossible, to find truly subquadratic time algorithms for these problems.

However, if we are willing to accept a good approximation (rather than the exact answer), then there has been significant progress in obtaining subquadratic algorithms on both the LIS and Edit Distance problems. This talk will survey some of this work.

What is the complexity of k-coloring graphs that do not contain a fixed graph H as an induced subgraph? It turns out that we can restrict our attention to the case when H is an induced subgraph of a path. I will talk about some recent results and open questions in this area. This is based on joint work with Maria Chudnovsky and Mingxian Zhong.