Joseph Slote

Joseph Slote, Alexander Volberg, Haonan Zhang

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 them through the lens of the \textit{Boolean surface area} (or Talagrand boundary): \[ \text{BSA}[f]={\mathbb E}|\nabla f| = {\mathbb E}|\sqrt{{Sens}_f(x)}, \] which is a natural measure of vertex-boundary complexity on the discrete cube. Our main result is that every degree-$d$ PTF $f$ has subpolynomial Boolean surface area: \[ \text{BSA}[f]\le \exp(C(d)\sqrt{\log n}). \] This is a superpolynomial improvement over the previous bound of $n^{1/4}(\log n)^{C(d)}$ that follows from Kane's landmark bounds on average sensitivity of PTFs \cite{DK}.

Matthias C. Caro, Preksha Naik, Joseph Slote

Properties of Boolean functions can often be tested much faster than the functions can be learned. However, this advantage usually disappears when testers are limited to random samples of a function $f$--a natural setting for data science--rather than queries. In this work we initiate the study of a quantum version of this "data science scenario": quantum algorithms that test properties of $f$ solely from quantum data in the form of copies of the function state $|f\rangle \propto \sum_x|x,f(x)\rangle$. $\bullet$ New tests. For three well-established properties--monotonicity, symmetry, and triangle-freeness--we show that the speedup lost when restricting classical testers to sampled data can be recovered by quantum algorithms operating solely from quantum data. $\bullet$ Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and we show that this necessary. In particular, there is no constant-complexity tester for symmetry relying solely on Fourier sampling and random classical samples. $\bullet$ Classical queries vs. quantum data. We exhibit a testing problem that can be solved from $O(1)$ classical queries but that requires $Ω(2^{n/2})$ function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. $\bullet$ Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of Goldreich et al. (2000) and Black (2023), which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.