Low-depth Boolean threshold circuits play an important role in theoretical computer science. On one hand, they are central for some of the main current frontiers in Boolean circuit complexity, and on the other hand they form a Boolean version of feed-forward neural networks. It turns out that proving lower bounds for these Boolean circuits is notoriously hard: lower bounds for explicit functions are unknown even for depth-2 circuits. In other words, we do not understand well the expressibility of feed-forward neural networks with just one hidden layer.

In this talk we will discuss known approaches to this problem, subproblems that also remain open, and some recent progress on them. In particular, we will discuss other computational models that turn out to be related to this setting, including models based on decision lists and models based on nearest neighbour representation of Boolean functions.

The talk is based on joint work with Mason DiCicco, Daniel Reichman and Morgan Prior. I will also mention some older results of joint work with Kristoffer Arnsfelt Hansen.

Vladimir Podolskii is a theoretical computer scientist working in computational complexity. He is currently an associate professor at Tufts University. Prior to that he has worked at Steklov Mathematical Institute in Moscow since 2009 as research scientist. From 2014 till 2022 he also worked at HSE University in Moscow as an associate professor (part-time). From 2022 till 2023 we worked as visiting associate professor at Courant Institute, NYU. He received his PhD from Moscow State University in 2009.