Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Manuscript

The Chow parameters of a Boolean function f: {−1, 1}n → {−1, 1} are its n + 1 degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Cho61, Tan61] that the (exact values of the) Chow parameters of any linear threshold function f uniquely specify f within the space of all Boolean functions, but until recently [OS11] nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function f, runs in time Õ(n2)· (1/)O(log 2(1/)) and with high probability outputs a representation of an LTF f ′ that is -close to f in Hamming distance. The only previous algorithm [OS11] had running time poly(n) · 22Õ(1/2). As a byproduct of our approach, we show that for any linear threshold function f over {−1, 1}n, there is a linear threshold function f ′ which is -close to f and has all weights that are integers of magnitude at mos