A huge part of basic computer logic is actually way simpler and more restricted than mathematicians have been saying for decades.
April 10, 2026
Original Paper
The Boolean surface area of polynomial threshold functions
arXiv · 2604.08095
The Takeaway
By proving a much tighter bound on the surface area of polynomial threshold functions, this work drastically limits the complexity of these models. This discovery means that learning these functions requires significantly less data and computational power than previously estimated.
From the 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 t