# School of Mathematics

## Fooling intersections of low-weight halfspaces

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).$

## High density phases of hard-core lattice particle systems

## Weinstein manifolds through skeletal topology

## Quasi-periodic solutions to nonlinear PDE's

## A converse theorem of Gross-Zagier and Kolyvagin: CM case

## Nematic liquid crystal phase in a system of interacting dimers

## On the strength of comparison queries

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries. This settles a problem studied by [Meyer auf der Heide ’84, Meiser ‘93, Erickson ‘95, Ailon and Chazelle ‘05, Gronlund and Pettie '14, Gold and Sharir ’15, Cardinal et al '15, Ezra and Sharir ’16] and others.

## Motivic correlators and locally symmetric spaces II

According to Langlands, pure motives are related to a certain class of automorphic representations.

Can one see mixed motives in the automorphic set-up? For examples, can one see periods of mixed motives in entirely automorphic terms? The goal of this and the next lecture is to supply some examples.

We define motivic correlators describing the structure of the motivic fundamental group $\pi_1^{\mathcal M}(X)$ of a curve. Their relevance to the questions raised above is explained by the following examples.