Learning and Lower Bounds for AC^0 with Threshold Gates.
P. Gopalan and R. Servedio.
In 14th Intl. Workshop on Randomization and Computation (RANDOM), 2010, pp. 588-601.


In 2002 Jackson \etal \cite{JKS:02} asked whether $\ACO$ 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 \cite{LMN:93} learns such circuits in sub-exponential time. Under a conjecture of Gotsman and Linial \cite{GL:94} which upper bounds the total influence of low-degree polynomial threshold functions, the running time is quasi-polynomial. Our results extend to $\ACO$ 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 $\ACO$ 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 \cite{DRST:09, HKM:09, Sherstov:09} on polynomial threshold functions.

Link to full version on the ECCC

Back to main papers page