Open Collections

Description

A simple way to generate a Boolean function in n variables is to take the sign of some polynomial. Such functions are called polynomial threshold functions. How many low-degree polynomial threshold functions are there? This problem was solved for degree $d=1$ by Zuev in 1989 and has remained open for any higher degrees, including $d=2$, since then. In a joint work with Pierre Baldi (UCI), we settle the problem for all degrees $d>1.$ The solution explores connections of Boolean functions to additive combinatorics and high-dimensional probability. This leads to a program of extending random matrix theory to random tensors, which is mostly an uncharted territory at present.