Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Ryan speaking today at Combinatorics Seminar

Gregory Valiant gvaliant at cs.stanford.edu
Thu Apr 7 13:24:26 PDT 2016


Hi Friends,

Ryan will be speaking at the combinatorics seminar, just before the
Motwani Colloquium.  Details below:

Speaker: Ryan Williams (Stanford)
Title: Super-Linear Gate and Super-Quadratic Wire Lower Bounds for
Depth-Two and Depth-Three Threshold Circuits
When: 3-4pm today
Where 384-H

Abstract: Low-depth threshold circuits provide a clean way to model
low-depth neural networks. For an explicit function in P, 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, as well as depth-three threshold circuits with
small weights. 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


More information about the theory-seminar mailing list