期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give tight bounds on the degree homogenous parts f of a bounded function f on the cube. We show that if f:1n[−11] has degree d, then f is bounded by d! , and f1 is bounded by de2+1n2−1 . We describe applications to pseudorandomness and learning theory. We use similar methods to generalize the classical Pisier's inequality from convex analysis. Our analysis involves properties of real-rooted polynomials that may be useful elsewhere.
