Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Learning and Lower Bounds for AC0 with threshold gates

Parikshit Gopalan and Rocco Servedio

Abstract

We give a learning algorithm for AC0 circuits augmented with a few thrshold gates, answering a question due to Jackson at al (2002). We prove a number of structural results and separations for such circuits.

Details

Publication typeInproceedings
Published inRANDOM'10
PublisherSpringer Verlag
> Publications > Learning and Lower Bounds for AC0 with threshold gates