Theory of Computing Seminar
Annenberg 107
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Ryan Williams,
Stanford,
Abstract:
Low-depth threshold circuits provide a clean way to model low-depth neural networks. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.
Joint work with Daniel Kane (UCSD). Paper available at http://arxiv.org/abs/1511.07860
For more information, please contact Thomas Vidick by email at [email protected].
Event Series
Theory of Computing Seminar Series