Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Anindya De*, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

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 Õ(n 2)· (1/ε) O(log2(1/ε)) and with high probability outputs a representation of an LTF f′ that is ε-close to f. The only previous algorithm [OS11] had running time poly(n) · 2 2Õ(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 at most √n · (1/ε) O(log2(1/ε)). This significantly improves the best previous result of [Serv09] which gave a poly(n) · 2 Õ(1/ε2/3) weight bound, and is close to the known lower bound of max{√n, (1/ε) Ω(log log (1/ε))} [Gol06,Serv07]. Our techniques also yield improved algorithms for related problems in learning theory. In addition to being significantly stronger than previous work, our results are obtained using conceptually simpler proofs. The two main ingredients underlying our results are (1) a new structural result showing that for f any linear threshold function and g any bounded function, if the Chow parameters of f are close to the Chow parameters of g then f is close to g; (2) a new boosting-like algorithm that given approximations to the Chow parameters of a linear threshold function outputs a bounded function whose Chow parameters are close to those of f.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages729-746
Number of pages18
DOIs
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

Keywords

  • boolean function
  • chow parameters
  • fourier analysis
  • threshold function

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces'. Together they form a unique fingerprint.

Cite this