The estimates for Boolean surface area of polynomial threshold functions
Fan Chang, Joseph Slote, Chun-Kai Tseng, 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 recently solved by OpenAI, \cite{GLsol}. In this work we study PTFs through the lens of the Boolean surface area (or Talagrand boundary) \[ \mathbf{BSA}[f]=\mathbb{E}|\nabla f|=\mathbb{E}\sqrt{s_{f}(x)}, \] a natural measure of vertex-boundary complexity on the discrete cube. Our main result is that every degree-$d$ PTF has polylogarithmic Boolean surface area: \[ \mathbf{BSA}[f]\le C_d(\log(en))^{C_d}. \] The proof is based on the PTF Restriction Lemma of Kabanets, Kane, and Lu \cite{KKL2017} and proceeds through a tail bound for the pointwise sensitivity. In particular, it controls all subcritical fractional moments of the sensitivity. We also record a random block partition principle for Boolean surface area and an alternative recursive argument following Kane's work \cite{DK} on average sensitivity, which independently yields the second bound \[ \mathbf{BSA}[f]\le \exp(C(d)\sqrt{\log n}). \] This bound was obtained in \cite{FSVZ} without clarifying the magnitude of $C(d)$, which we do below. For lower moments $\bE |\nabla f|^η \le C(d, η)$ there is no dependence on $n$ for $0<η<1$.
尚无 AI 解读，展示原文摘要