[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars -- Week of October 30, 2017

[Anthony V. Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of October 30, 2017


--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------

Monday, October 30

Computer Science/Discrete Mathematics Seminar I
Topic: 		Fooling intersections of low-weight halfspaces
Speaker: 	Rocco Servedio, Columbia University
Time/Room: 	11:00am - 12:15pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=128784



Tuesday, October 31

Computer Science/Discrete Mathematics Seminar II
Topic: 		Cap-sets in $(F_q)^n$ and related problems
Speaker: 	Zeev Dvir, Princeton University; von Neumann Fellow, School of Mathematics
Time/Room: 	10:30am - 12:30pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=129016

1 Fooling intersections of low-weight halfspaces
    Rocco Servedio

A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 
+ \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in 
$\{-t,\dots,t\}.$  We give an explicit pseudorandom generator that 
$\delta$-fools any intersection of $k$ weight-$t$ halfspaces with seed 
length poly$(\log n, \log k,t,1/\delta)$. In particular, our result 
gives an explicit PRG that fools any intersection of any quasipoly$(n)$ 
number of halfspaces of any polylog$(n)$ weight to any $1/$polylog$(n)$ 
accuracy using seed length polylog$(n).$

Prior to this work no explicit PRG with seed length $o(n)$ was known 
even for fooling intersections of $n$ weight-1 halfspaces to constant 
accuracy.

Our analysis introduces new coupling-based ingredients into the standard 
Lindeberg method for establishing quantitative central limit theorems 
and associated pseudorandomness results.

Joint work with Li-Yang Tan.

http://www.math.ias.edu/seminars/abstract?event=128784

2 Cap-sets in $(F_q)^n$ and related problems
    Zeev Dvir

A cap set in $(F_q)^n$ is a set not containing a three term arithmetic 
progression. Last year, in a surprising breakthrough, Croot-Lev-Pach and 
a follow up paper of Ellenberg-Gijswijt showed that such sets have to be 
of size at most $c^n$ with $c < q$ (as $n$ goes to infinity). The simple 
algebraic proof of this result has since led to new progress and 
insights on several other related problems in combinatorics and 
theoretical computer science. In this survey I will describe these 
results including some new work (joint with B. Edelman) relating to 
matrix rigidity.

http://www.math.ias.edu/seminars/abstract?event=129016

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu