Rocco Servedio awarded NSF grant to study limits of computing

Rocco Servedio, Associate Professor of Computer Science, and his former student Li-Yang Tan (PhD ’14) are recipients of a four-year, $1.2M National Science Foundation (NSF) Award for their proposal to use random projections to prove lower bounds on Boolean circuits. The award will allow Servedio and Tan, now on the faculty of Toyota Technological Institute at Chicago, to continue work they started last year in their paper “An average-case depth hierarchy theorem for Boolean circuits.” Named Best Paper at the FOCS 2015 conference, it resolved a conjecture that had been open for close to 30 years.

“I’m grateful to receive this award and excited to continue working on circuit lower bounds,” says Servedio. “A big part of computer science aims at inventing new algorithms to extend what computers can do, but there are limits to what tasks computers can perform efficiently, and it’s important to understand those limits. This grant will allow us to more thoroughly study this question while giving graduate students the opportunity to be involved in this research at an early stage. ”

Similar to physicists probing the laws of nature to know what is possible in the physical world, theoretical computer scientists working in the field of computational complexity aim to understand the inherent limitations of efficient computing. The ultimate goal of this line of work is to prove mathematically that computers cannot efficiently solve certain problems no matter how cleverly they are programmed. Proving lower bounds on Boolean circuits (a mathematical abstraction of the digital circuits that computers are built from) is an important topic in computational complexity.

After an early burst of progress on circuit lower bounds in the 1980s, research advances in this area have been few and far between. The main challenge facing researchers in this area is establishing a negative: how is it possible to rule out the existence of some clever, unexpected approach to solve a computational problem (a small Boolean circuit capturing some as-yet-unthought-of algorithmic insight)?

Servedio and Tan will employ the method of random projections introduced in their FOCS paper. Random projections are an extension of random restrictions, a method of proving circuit lower bounds that was responsible for much of the progress made in the 1980s. Roughly speaking, random restrictions work by randomly fixing some input variables to randomly chosen constant values. If C is a circuit that is supposed to compute some function f, it is sometimes possible to show that (i) applying a random restriction to C simplifies C “a lot”, while (ii) applying the same random restriction to f only causes it to simplify “a little.”   This can lead to a contradiction, since it may be possible to show that a “greatly simplified” circuit cannot compute a “still-complex” function–if this is indeed the case, then the original circuit C could not actually have computed the function f correctly, which gives the desired circuit lower bound.

The random projection method shows some promise in revitalizing this line of research. The method works similarly to random restrictions but further generalizes the approach by identifying certain sets of variables in a careful way and setting them all to the same value (i.e., “projecting” a set of distinct input variables to a common new variable). These variable identifications enable a further level of “control”  that can be useful in arguing that the function f “stays complex” after the random projection (while the circuit C “still simplifies a lot”). Random projections were at the heart of the circuit lower bound established by Servedio and Tan in their FOCS paper; supported by this grant, they will search for other applications of random projections.

Circuit lower bounds obtained via this work may help guide algorithm development away from dead ends. It may also deepen our fundamental understanding of computation.

“Sometimes work on circuit lower bounds can double back and help us to develop new algorithms and models,” says Servedio. “To establish limits on the power of different types of circuits, you have to really understand what those types of circuits can do, and this understanding can be helpful for solving other problems and developing new algorithms.”

Posted 4/25/2016