The Boolean surface area of polynomial threshold functions

Alexander Volberg; Fan Chang; Haonan Zhang; Joseph Slote

arxiv: 2604.08095 · v2 · submitted 2026-04-09 · 💻 cs.CC · math.AP· math.CA· math.PR

The Boolean surface area of polynomial threshold functions

Fan Chang , Joseph Slote , Alexander Volberg , Haonan Zhang This is my paper

Pith reviewed 2026-05-10 17:46 UTC · model grok-4.3

classification 💻 cs.CC math.APmath.CAmath.PR

keywords polynomial threshold functionsBoolean surface areaTalagrand boundarysensitivityBoolean functionshypercube isoperimetrydegree dlearning theory

0 comments

The pith

Every degree-d polynomial threshold function has polylogarithmic Boolean surface area.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an upper bound on the Boolean surface area of any degree-d polynomial threshold function, showing the measure is at most C_d times (log(en)) raised to a power that depends only on d. A sympathetic reader would care because this surface area equals the expected square root of the function's sensitivity and therefore quantifies the average size of the function's boundary on the hypercube more sharply than average sensitivity alone. The proof obtains a tail bound on pointwise sensitivity and thereby controls all subcritical fractional moments of that sensitivity; a separate recursive argument recovers a weaker but still subexponential bound. The result extends the line of structural work on low-degree threshold functions that began with questions about their average sensitivity.

Core claim

The central claim is that for every polynomial threshold function f of degree d the Boolean surface area BSA[f], defined as the expectation of the square root of the sensitivity s_f(x), is bounded above by C_d (log(en))^{C_d}. The argument proceeds by deriving a tail bound on the random variable s_f(x) that is strong enough to control every fractional moment of order less than one, then integrating to bound the square-root expectation. An independent recursive argument following earlier sensitivity work yields the weaker but still explicit bound BSA[f] ≤ exp(C_d √(log n)).

What carries the argument

A tail bound on the pointwise sensitivity of degree-d polynomial threshold functions, obtained via a restriction principle, that suffices to bound every subcritical fractional moment and therefore the expectation of the square root.

Load-bearing premise

The restriction principle for polynomial threshold functions must supply tail bounds on sensitivity strong enough to control all fractional moments below order one.

What would settle it

A concrete degree-d polynomial threshold function on n variables whose Boolean surface area grows faster than every polylogarithmic function of n, for example linearly in log n or as (log n)^k for arbitrarily large k.

read the original abstract

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 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 weaker bound \[ \mathbf{BSA}[f]\le \exp(C_d\sqrt{\log n}). \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a new polylog bound on Boolean surface area for degree-d PTFs by applying the KKL restriction lemma to sensitivity moments, plus a weaker self-contained alternative.

read the letter

The main point is that every degree-d PTF has Boolean surface area at most C_d (log(en)) to some power in d. That is the new claim, and it improves on the exp(C_d sqrt(log n)) bound the authors also derive via a recursive argument in the style of Kane's earlier sensitivity work. They reach the stronger bound by using the 2017 Kabanets-Kane-Lu restriction lemma to control all subcritical fractional moments of the pointwise sensitivity, then integrating to bound the expectation of its square root. They also record a random block partition principle for surface area along the way. That package is the concrete contribution. The approach is direct and stays inside the existing toolkit for PTFs, which is a plus. The alternative recursive bound is useful because it does not lean on the restriction lemma at all, so readers can compare the two routes. The citation pattern is clean; the authors cite the relevant prior results on average sensitivity and restrictions without padding. The soft spot is that the polylog result depends on the 2017 lemma supplying uniform quantitative control over those fractional moments for every degree-d PTF. The abstract says the lemma is applied with sufficient strength, but if the constants or the range of p < 1 do not line up exactly, the tail bound step could weaken. The authors do not strengthen the lemma themselves, so the main claim inherits whatever gaps exist in the prior work. The weaker bound shows they are aware of this dependency. This paper is for people who work on isoperimetric properties of low-degree Boolean functions or on learning and testing algorithms that use sensitivity bounds. A reader following the Gotsman-Linial line would get value from the explicit polylog statement. It deserves a serious referee because the claim is specific, the proof sketch is checkable against the cited lemma, and the alternative argument provides an independent data point. I would send it to review.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that every degree-d polynomial threshold function f on the Boolean cube satisfies a polylogarithmic bound on its Boolean surface area: BSA[f] = E[sqrt(s_f(x))] ≤ C_d (log(en))^{C_d}. The proof proceeds by deriving a tail bound on the pointwise sensitivity random variable s_f(x) via the PTF Restriction Lemma of Kabanets, Kane, and Lu (2017), which is asserted to control all subcritical fractional moments E[s_f(x)^p] for p < 1. The paper also records a random block partition principle and gives an alternative recursive argument (following Kane's prior work on average sensitivity) that yields the weaker bound exp(C_d √log n).

Significance. If the main polylogarithmic bound is rigorously established, the result would strengthen the isoperimetric theory of PTFs by providing near-optimal control on the Talagrand boundary measure, with potential applications to learning and testing algorithms. The inclusion of both the primary proof route (via the external Restriction Lemma) and a self-contained recursive alternative is a clear strength, as the latter permits independent verification of a weaker but still nontrivial bound without external quantitative assumptions.

major comments (2)

[Abstract (proof sketch via Restriction Lemma)] Abstract (proof sketch via Restriction Lemma): The central claim BSA[f] ≤ C_d (log(en))^{C_d} is obtained by integrating a tail bound on s_f(x) that in turn requires the KKL2017 Restriction Lemma to supply uniform quantitative control on E[s_f(x)^p] for every p < 1. The manuscript states only that the lemma is applied “with sufficient strength,” without specifying the admissible range of p, the resulting tail decay rate, or an explicit verification that the lemma’s hypotheses hold uniformly for all degree-d PTFs. This step is load-bearing; the alternative recursive argument recovers only the weaker exp(C_d √log n) bound.
[Main result and tail-bound integration] Main result and tail-bound integration: No explicit constants or functional dependence of C_d on d are derived from the moment bounds; while existential dependence on d is acceptable, the absence of even a sketch of how the fractional-moment control translates into the precise polylog exponent leaves the quantitative strength of the theorem unverified from the given text.

minor comments (2)

[Abstract] The random block partition principle is announced but receives no statement or proof sketch in the abstract; a one-sentence description of the principle and its role would improve readability.
[Notation] Notation: The pointwise sensitivity s_f(x) and the gradient notation |∇f| are used without an inline reminder of their definitions; a brief parenthetical reference to the standard Boolean-cube definitions would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. The comments identify opportunities to strengthen the presentation of the main proof. We address each major comment below and will revise the manuscript to incorporate additional details as outlined.

read point-by-point responses

Referee: [Abstract (proof sketch via Restriction Lemma)] The central claim BSA[f] ≤ C_d (log(en))^{C_d} is obtained by integrating a tail bound on s_f(x) that in turn requires the KKL2017 Restriction Lemma to supply uniform quantitative control on E[s_f(x)^p] for every p < 1. The manuscript states only that the lemma is applied “with sufficient strength,” without specifying the admissible range of p, the resulting tail decay rate, or an explicit verification that the lemma’s hypotheses hold uniformly for all degree-d PTFs. This step is load-bearing; the alternative recursive argument recovers only the weaker exp(C_d √log n) bound.

Authors: We agree that the application of the PTF Restriction Lemma requires more explicit elaboration to make the argument self-contained. In the revised manuscript we will specify the admissible range of p < 1 for which the lemma supplies moment control, state the resulting tail decay rate obtained for the sensitivity random variable s_f(x), and confirm that the lemma’s hypotheses hold uniformly across all degree-d PTFs. These additions will be placed in the proof section immediately following the invocation of the lemma, while the alternative recursive argument will remain as an independent, self-contained route yielding the weaker bound. revision: yes
Referee: [Main result and tail-bound integration] No explicit constants or functional dependence of C_d on d are derived from the moment bounds; while existential dependence on d is acceptable, the absence of even a sketch of how the fractional-moment control translates into the precise polylog exponent leaves the quantitative strength of the theorem unverified from the given text.

Authors: We acknowledge that an explicit sketch of the integration from fractional-moment bounds to the polylogarithmic surface-area bound would improve verifiability. In the revision we will insert a short derivation (approximately one paragraph) showing how control of E[s_f(x)^p] for p < 1 produces a tail bound on s_f(x) whose integration yields BSA[f] ≤ C_d (log(en))^{C_d}, with the dependence of C_d on d inherited from the quantitative parameters of the Restriction Lemma. We do not claim numerical values for C_d, but the added sketch will make the claimed functional dependence transparent. revision: yes

Circularity Check

0 steps flagged

No circularity detected; main bound uses external KKL2017 lemma as black box

full rationale

The paper derives its polylogarithmic BSA bound for degree-d PTFs by invoking the external PTF Restriction Lemma of Kabanets-Kane-Lu (2017) to control subcritical fractional moments of sensitivity, then integrating to obtain the tail bound and BSA estimate. The alternative exp(C_d √log n) bound follows a recursive argument modeled on Kane's prior work but does not feed back into the main result. No equation in the paper defines a quantity from its own outputs and then renames it as a prediction, nor does any load-bearing step reduce to a self-citation whose content is unverified within the manuscript. The cited lemmas are independent external results, so the derivation chain remains non-circular.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The result rests on the validity of the PTF Restriction Lemma and standard facts about Boolean sensitivity and fractional moments; C_d is an existential constant whose dependence on d is not computed explicitly.

free parameters (1)

C_d
Existence of a constant depending only on d is asserted; no explicit value or fitting procedure is given.

axioms (1)

domain assumption PTF Restriction Lemma (Kabanets, Kane, Lu 2017)
Invoked to reduce the problem and derive the tail bound on sensitivity.

pith-pipeline@v0.9.0 · 5568 in / 1265 out tokens · 39345 ms · 2026-05-10T17:46:34.563770+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

B. Chapman. The Gotsman--Linial conjecture is false. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA , pages 692--699, 2018

work page 2018
[2]

Diakonikolas, P

I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Y. Tan. Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. Proceedings of the Forty-Second ACM Symposium on Theory of Computing , pages 533--542, 2010

work page 2010
[3]

Concentration on the B oolean hypercube via pathwise stochastic analysis

Ronen Eldan and Renan Gross. Concentration on the B oolean hypercube via pathwise stochastic analysis. Invent. Math. , 230(3):935--994, 2022

work page 2022
[4]

Isoperimetric inequalities made simpler

Ronen Eldan, Guy Kindler, Noam Lifshitz, and Dor Minzer. Isoperimetric inequalities made simpler. Discrete Anal. , pages Paper No. 7, 23, 2025

work page 2025
[5]

Ivanisvili, R

P. Ivanisvili, R. Van Handel, and A. Volberg. Rademacher type and E nflo type coincide. Ann. of Math. (2) , 192(2):665--678, 2020

work page 2020
[6]

Daniel M. Kane. The Gaussian surface area and noise sensitivity of degree- d polynomial threshold functions. Comput. Complexity , 20(2):389--412, 2011

work page 2011
[7]

Daniel M. Kane. The correct exponent for the G otsman-- L inial conjecture. Comput. Complexity , 23(2):151--175, 2014

work page 2014
[8]

Kabanets, D

V. Kabanets, D. M. Kane, and Z. Lu. A polynomial restriction lemma with applications. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 615--628, 2017

work page 2017
[9]

Klivans, Ryan O'Donnell, and Rocco A

Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning geometric concepts via Gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science , pages 541--550. IEEE, 2008

work page 2008
[10]

G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredachi Informatsii , 10(2):101--108, 1974

work page 1974
[11]

Open Problems in Analysis of Boolean Functions

Ryan O'Donnell. Open problems in analysis of Boolean functions. arXiv preprint , arXiv:1204.6447, 2012

work page Pith review arXiv 2012
[12]

Noise stability of weighted majority

Yuval Peres. Noise stability of weighted majority. In In and out of equilibrium 3. Celebrating Vladas Sidoravicius , volume 77 of Progr. Probab. , pages 677--682. Birkhauser/Springer, Cham, [2020] 2021

work page 2020
[13]

Talagrand

M. Talagrand. Isoperimetry, logarithmic S obolev inequalities on the discrete cube, and M argulis' graph connectivity theorem. Geom. Funct. Anal. , 3(3):295--314, 1993

work page 1993

[1] [1]

B. Chapman. The Gotsman--Linial conjecture is false. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA , pages 692--699, 2018

work page 2018

[2] [2]

Diakonikolas, P

I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Y. Tan. Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. Proceedings of the Forty-Second ACM Symposium on Theory of Computing , pages 533--542, 2010

work page 2010

[3] [3]

Concentration on the B oolean hypercube via pathwise stochastic analysis

Ronen Eldan and Renan Gross. Concentration on the B oolean hypercube via pathwise stochastic analysis. Invent. Math. , 230(3):935--994, 2022

work page 2022

[4] [4]

Isoperimetric inequalities made simpler

Ronen Eldan, Guy Kindler, Noam Lifshitz, and Dor Minzer. Isoperimetric inequalities made simpler. Discrete Anal. , pages Paper No. 7, 23, 2025

work page 2025

[5] [5]

Ivanisvili, R

P. Ivanisvili, R. Van Handel, and A. Volberg. Rademacher type and E nflo type coincide. Ann. of Math. (2) , 192(2):665--678, 2020

work page 2020

[6] [6]

Daniel M. Kane. The Gaussian surface area and noise sensitivity of degree- d polynomial threshold functions. Comput. Complexity , 20(2):389--412, 2011

work page 2011

[7] [7]

Daniel M. Kane. The correct exponent for the G otsman-- L inial conjecture. Comput. Complexity , 23(2):151--175, 2014

work page 2014

[8] [8]

Kabanets, D

V. Kabanets, D. M. Kane, and Z. Lu. A polynomial restriction lemma with applications. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 615--628, 2017

work page 2017

[9] [9]

Klivans, Ryan O'Donnell, and Rocco A

Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning geometric concepts via Gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science , pages 541--550. IEEE, 2008

work page 2008

[10] [10]

G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredachi Informatsii , 10(2):101--108, 1974

work page 1974

[11] [11]

Open Problems in Analysis of Boolean Functions

Ryan O'Donnell. Open problems in analysis of Boolean functions. arXiv preprint , arXiv:1204.6447, 2012

work page Pith review arXiv 2012

[12] [12]

Noise stability of weighted majority

Yuval Peres. Noise stability of weighted majority. In In and out of equilibrium 3. Celebrating Vladas Sidoravicius , volume 77 of Progr. Probab. , pages 677--682. Birkhauser/Springer, Cham, [2020] 2021

work page 2020

[13] [13]

Talagrand

M. Talagrand. Isoperimetry, logarithmic S obolev inequalities on the discrete cube, and M argulis' graph connectivity theorem. Geom. Funct. Anal. , 3(3):295--314, 1993

work page 1993