Degreed Chow Parameters Robustly Determine Degreed PTFs (and Algorithmic Applications). The degreed Chow parameters of a Boolean function f: 1,1n to mathbbR are its degree at most d Fourier coefficients. It is wellknown that degreed Chow parameters uniquely characterize degreed polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degreed PTF and g any bounded function, if the degreed Chow parameters of f are close to the degreed Chow parameters of g in ell_2norm, then f is close to g in ell_1distance. Notably, our bound relating the two distances is completely independent of the dimension n. That is, we show that Boolean degreed PTFs are em robustly identifiable from their degreed Chow parameters. Results of this form had been shown for the d1 caseciteOS11:chow, DeDFS14, but no nontrivial bound was previously known for d u003e1.  robust :142,identifiability result gives the following algorithmic applications: First, we show that Boolean degreed PTFs can be efficiently approximately reconstructed from approximations to their degreed Chow parameters. This immediately implies that degreed PTFs are efficiently learnable in the uniform distribution dRFA modelciteBenDavidDichterman:98. As a byproduct of our approach, we also obtain the first low integerweight approximations of degreed PTFs, for du003e1. As our second application, our robust :142,identifiability result gives the first efficient algorithm, with dimensionindependent error guarantees, for malicious learning of Boolean degreed PTFs under the uniform distribution.

Approximating the noise sensitivity of a monotone Boolean function The noise sensitivity of a Boolean function f: 0,1n rightarrow 0,1 is one of its fundamental properties. A function of a positive noise parameter delta, it is denoted as NS_deltaf. Here we study the algorithmic problem of approximating it for monotone f, such that NS_deltaf geq 1nC for constant C, and where delta satisfies 1n leq delta leq 12. For such f and delta, we give a randomized algorithm performing Oleft(fracmin(1,sqrtn delta log1.5 n) NS_deltaf textpolyleft(frac1epsilonright)right) queries and approximating NS_deltaf to within a multiplicative factor of (1pm epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omegaleft(fracmin(1,sqrtn delta)NS_deltaf cdot nxiright) on the query complexity of any algorithm that approximates NS_deltaf to within any constant factor, where xi can be any positive constant. Thus, our algorithmu0027s query complexity is close to optimal in terms of its dependence on n.  :145,introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of thin functions with certain properties. The existence of such thin functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.