Counting Boolean functions defined by polynomial sign patterns
Logarithmic asymptotics for polynomial threshold functions
Discrete MathematicsInformation Theory
Summary
This paper looks at how many different Boolean functions you can make by looking at whether a polynomial with limited complexity is positive or negative when you plug in true/false values. The authors show that the number of these functions matches previous best estimates very closely as the number of variables grows. They use a mix of probability, coding theory, and algebraic techniques to get precise formulas for these counts. This helps understand the complexity and diversity of functions represented by polynomial thresholds.
What this means in practice
- •For complexity theorists: Clarifies limits on how many functions polynomial threshold circuits of bounded degree can represent, helping analyze circuit complexity.
- •For machine learning researchers: Informs the theoretical understanding of classifier capacity by quantifying how many decision boundaries degree-bounded polynomials can define.
A theory result. No direct application yet.
Authors
Martin Anthony
Abstract
We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.