Title: A Regularity Lemma, and Low-weight Approximators, for Low-degree
Polynomial Threshold Functions
Speaker: Andrew Wan, Columbia
Abstract:
We give a “regularity lemma” for degree-d polynomial threshold
functions (PTFs) over the Boolean cube {?1, 1}^n. Roughly speaking,
this result shows that every degree-d PTF can be decomposed into a
constant number of subfunctions such that almost all of the
subfunctions are close to being regular PTFs. Here a “regular” PTF is
a PTF sign(p(x)) where the in?uence of each variable on the polynomial
p(x) is a small fraction of the total in?uence of p.
Roughly speaking, regular PTFs are useful because they inherit
certain nice properties of PTFs over Gaussian (rather than Boolean)
inputs; this intuition can be made precise using the "invariance
principle" of Mossel et al. ("Noise Stability of functions with low
influences: invariance and optimality," FOCS 05).
This point of view has been used to obtain a wide variety of results
for the degree one case,
and more recently to obtain new results for larger degree (average
sensitivity bounds, pseudorandomness against PTFs, etc.).
Our regularity lemma provides a way to reduce questions about
arbitrary PTFs to ones about regular PTFs.
As an application, we prove that for any constants d ? 1, ? > 0, every
degree-d PTF over n variables can be approximated to accuracy ? by a
constant-degree PTF that has
integer weights of total magnitude O(nd ).