Polynomial threshold functions, hyperplane arrangements, and random tensors
Skip to main content
eScholarship
Open Access Publications from the University of California

Polynomial threshold functions, hyperplane arrangements, and random tensors

  • Author(s): Baldi, Pierre
  • Vershynin, Roman
  • et al.
Creative Commons 'BY' version 4.0 license
Abstract

A simple way to generate a Boolean function is to take the sign of a real polynomial in $n$ variables. Such Boolean functions are called polynomial threshold functions. How many low-degree polynomial threshold functions are there? The partial case of this problem for degree $d=1$ was solved by Zuev in 1989, who showed that the number $T(n,1)$ of linear threshold functions satisfies $\log_2 T(n,1) \approx n^2$, up to smaller order terms. However the number of polynomial threshold functions for any higher degrees, including $d=2$, has remained open. We settle this problem for all fixed degrees $d \ge1$, showing that $ \log_2 T(n,d) \approx n \binom{n}{\le d}$. The solution relies on connections between the theory of Boolean threshold functions, hyperplane arrangements, and random tensors. Perhaps surprisingly, it uses also a recent result of E.Abbe, A.Shpilka, and A.Wigderson on Reed-Muller codes.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View