Almost all Boolean functions need midpoint degree polynomials
Almost every Boolean function has central threshold degree
Discrete MathematicsInformation Theory
Summary
The authors studied how complex it is to represent Boolean functions using polynomials that output positive or negative signs matching the function. They found that for most Boolean functions with many variables, the minimum polynomial degree needed is almost exactly half the number of variables. This result sharpens understanding of how complex Boolean functions can be from a polynomial perspective. The proof connects this problem to ideas in error-correcting codes and probabilistic thresholds.
What this means in practice
- •For circuit designers: Assess fundamental limits on polynomial-based representations that impact designing efficient Boolean logic approximations.
- •For coding theory engineers: Use connections between polynomial threshold degree and Reed–Muller codes recovery to improve error-correcting decoding strategies.
A theory result. No direct application yet.
Authors
Martin Anthony
Abstract
The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.