[theory-seminar] Ryan speaking today at Combinatorics Seminar

[Gregory Valiant]

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