BARC talk by Vladimir Podolskii

Tuesday, September 29, 2026, 13:30-14:30, Vladimir Podolskii, Associate Professor at Tufts University, USA, will be giving a BARC talk on "Depth-2 threshold circuits and related models of computation".

Abstract:
Low-depth Boolean threshold circuits play an important role in computational complexity. In particular, they form one of the main current frontiers in Boolean circuit complexity. 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 this talk Vladimir will discuss known approaches to this problem, subproblems that also remain open, and some recent progress on them. In particular, Vladimir will discuss other computational models that turn out to be related to this setting, including models based on decision lists.

The talk is based on joint work with Morgan Prior. Vladimir will also mention some older results of joint work with Kristoffer Arnsfelt Hansen. If time permits he will also discuss results of joint work with Mason DiCicco and Daniel Reichman.

Bio:
Vladimir Podolskii is an Associate Professor of Computer Science and an Associate Professor of Mathematics at the Tufts University in Massachusetts, USA. His areas of interest include computational complexity, logical foundations of computer science, tropical geometry. Vladimir earned his PhD at the Lomonosov Moscow State University, Moscow, Russia, in 2009

Host:
Srikanth Srinivasan