Synopsis

This Quarterly Theory Workshop is on the theme of analytic methods in
computer science. In the last two decades, methods from mathematical
analysis have resulted in breakthroughs in the otherwise `discrete
world of theoretical computer science’. The speakers Ryan O’Donnell,
Oded Regev and Li-Yang Tan will speak about fundamental problems in
complexity theory, quantum computing and lattices which have succumbed
to these methods.

Logistics 

• Location: Ruan Transportation Center, Chambers Hall (basement level) (map), 600 Foster Street, Evanston, IL 60208.
• Transit: Noyes St. Purple Line (map).
• Parking: Validation for North Campus Parking Garage (map) available at workshop.

Registration 

Registration is free. Please register at https://goo.gl/forms/wpkRhkaEiznvSfIr2 if you plan to attend.

Schedule

Titles and Abstracts

Speaker: Ryan O’Donnell, Carnegie Mellon University (CMU)
Title: Statistics of longest increasing subsequences and quantum states

Abstract: Suppose you have access to i.i.d. samples from an unknown probability
distribution $p = (p_1, …, p_d)$ on $[d]$, and you want to learn or
test something about it. For example, if you want to estimate $p$
itself, then the empirical distribution will suffice when the number
of samples, $n$, is $O(d/epsilon^2)$. In general, you can ask many
more specific questions about $p$: Is it close to some known
distribution $q$? Does it have high entropy? Etc. For many of these
questions the optimal sample complexity has only been determined over
the last $10$ years in the computer science literature.

The natural quantum version of these problems involves being given
samples of an unknown $d$-dimensional quantum mixed state $\rho$,
which is a positive $d \times d$ matrix with trace $1$. Many questions
from learning and testing probability carry over naturally to this
setting: for example, estimating $\rho$ (the problem of “quantum
tomography/state-learning”); or, testing if $\rho$ is close to a fixed
state (the problem of “quantum
hypothesis-testing/state-certification”).

Surprisingly, the analysis of these quantum problems mostly reduces to
questions concerning the combinatorics of longest increasing
subsequences (LISes) in random words. In particular, a key technical
question that needs to be faced is this: given a random word $w \in
[d]^n$, where each letter $w_i$ is drawn i.i.d. from some distribution
$p$, what do we expect $\mathrm{LIS}(w)$ to be? Answering this
question requires diversions into the Robinson–Schensted–Knuth
algorithm, representation theory of the symmetric group, the theory of
symmetric polynomials, and many other interesting areas.

Speaker: Li-Yang Tan, Toyota Technological Institute (TTI) at Chicago
Title: Fooling intersections of low-weight halfspaces

Abstract: A weight-t halfspace is a Boolean function f(x)=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 non-trivial seed length was known even for fooling
intersections of n weight-1 halfspaces to constant accuracy.

The analysis of our PRG fuses techniques from two different lines of work on
unconditional pseudorandomness for different kinds of Boolean functions. We
extend the approach of Harsha, Klivans, and Meka for fooling
intersections of regular halfspaces, and combine this approach with results of
Bazzi and Razborov on bounded independence
fooling CNF formulas. 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 Rocco Servedio.

Speaker: Oded Regev, Courant Institute, New York University (NYU).
Title: A Reverse Minkowski Theorem

Abstract: Informally, Minkowski’s first theorem states that lattices that are
globally dense (have small determinant) are also locally dense (have
lots of points in a small ball around the origin). This fundamental
result dates back to 1891 and has a very wide range of applications.

I will present a proof of a reverse form of Minkowski’s theorem,
conjectured by Daniel Dadush in 2012, showing that locally dense
lattices are also globally dense (in the appropriate sense).

The talk will be self contained and I will not assume any familiarity
with lattices. Based on joint papers with Daniel Dadush and Noah Stephens-Davidowitz.