# QTW Workshop on Analytic Methods in Computer Science

**About the Series**

**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.

**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.

## Recent Comments