Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-074 | 20th April 2010 21:58

Learning and Lower Bounds for AC$^0$ with Threshold Gates


Authors: Parikshit Gopalan, Rocco Servedio
Publication: 21st April 2010 22:45
Downloads: 1969


In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan [LMN93] learns such circuits in sub-exponential time. Under a conjecture of Gotsman and Linial [GL94] which upper bounds the total influence of low-degree polynomial threshold functions, the running time is quasi-polynomial. Our results extend to AC0 circuits augmented with a small super-constant number of threshold gates at arbitrary locations in the circuit. We also establish some new structural properties of AC$^0$ circuits augmented with threshold gates, which allow us to prove a range of separation results and lower bounds.

Our techniques combine classical random restriction arguments with more recent results [DRST09,
HKM09, She09] on polynomial threshold functions.

ISSN 1433-8092 | Imprint