The Boolean surface area of polynomial threshold functions
2026-04-09 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study polynomial threshold functions (PTFs), which are special types of Boolean functions important in learning and approximation. They focus on a new way to measure the complexity of PTFs called Boolean surface area, which captures how complicated the boundary of these functions is when viewed as points on a cube. Their main discovery is that this boundary complexity grows very slowly, much slower than previously known estimates. This result improves our understanding of how tightly PTFs are constrained geometrically.
Polynomial threshold functionsBoolean functionsBoolean surface areaTalagrand boundaryAverage sensitivityIsoperimetric inequalitiesDiscrete cubeGotsman–Linial conjectureLearning theoryApproximation theory
Authors
Joseph Slote, Alexander Volberg, Haonan Zhang
Abstract
Polynomial threshold functions (PTFs) are an important low-complexity class of Boolean functions, with strong connections to learning theory and approximation theory. Recent work on learning and testing PTFs has exploited structural and isoperimetric properties of the class, especially bounds on average sensitivity, one of the central themes in the study of PTFs since the Gotsman--Linial conjecture. In this work we exhibit a new geometric sense in which PTFs are tightly constrained, by studying them through the lens of the \textit{Boolean surface area} (or Talagrand boundary): \[ \text{BSA}[f]={\mathbb E}|\nabla f| = {\mathbb E}|\sqrt{{Sens}_f(x)}, \] which is a natural measure of vertex-boundary complexity on the discrete cube. Our main result is that every degree-$d$ PTF $f$ has subpolynomial Boolean surface area: \[ \text{BSA}[f]\le \exp(C(d)\sqrt{\log n}). \] This is a superpolynomial improvement over the previous bound of $n^{1/4}(\log n)^{C(d)}$ that follows from Kane's landmark bounds on average sensitivity of PTFs \cite{DK}.