Boolean Circuit Complexity and Its Applications

Abstract

Circuit complexity is an old branch of computer science, dating back to the late 1940s. The original motivation for the circuit model was related to the studies of electrical circuits. The area of circuit complexity gained a lot of interest in the end of 1970s, mainly in the context of proving lower bounds. It was observed that strong lower bounds for circuit complexity of explicitly given functions would imply that P is not equal to NP. However, proving lower bounds for the boolean circuit model turned out to be extremely hard and only linear lower bounds for explicit functions are currently known. The main progress in this area is related to the studies of restricted classes of circuits: celebrated results in the 1980s showed strong lower bounds for monotone circuits and for circuits of bounded depth. These classes of circuits are interesting on their own, for example, bounded depth circuits model highly parallelizable computations. But more importantly, the fundamental idea in this area is to introduce new methods and techniques for restricted classes of circuits with the hope that eventually this will lead to breakthroughs for unrestricted circuits and other computational models. The area of circuit complexity has developed in this paradigm since then with many beautiful results both in new lower bound techniques and barriers for proving such lower bounds.

Studies of bounded depth circuits singled out threshold circuits as one of the main current frontiers for lower bounds in circuit complexity model. In the talk we will devote special attention to this class and review some recent progress. Apart from their relevance to circuit complexity, threshold circuits are also related to learning theory as they can be viewed as a boolean version of feed-forward neural networks. We will also mention some applications of threshold circuits in cryptography.

Next we will discuss applications of boolean circuit complexity in database theory. More specifically, we will discuss query answering problem for the databases augmented with logical theories. Surprisingly, circuit complexity can help to prove lower bounds in this setting and the results on monotone boolean circuit complexity turn out to be of great importance here.

Bio Vladimir Podolskii is a theoretical computer scientist whose main research interests are computational complexity, logical foundations of computer science, min-plus geometry. He is currently a visiting associate professor at Courant Institute, NYU. Prior to that he has worked at Steklov Mathematical Institute in Moscow since 2009 as leading research scientist (currently on leave). From 2014 till 2022 he also worked at HSE University in Moscow as an associate professor (part-time) where he also served as Head of Big Data and Information Retrieval School from 2015 to 2022. He received his PhD from Moscow State University in 2009.