Learning and Lower Bounds for AC0 with threshold gates

  • Parikshit Gopalan ,
  • Rocco Servedio

RANDOM'10 |

Published by Springer Verlag

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