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 ).