# School of Mathematics

## An introduction to Boolean Function Analysis

We will discuss some of the basic principles and results in the study of Boolean-valued functions over the discrete hypercube using discrete Fourier analysis. In particular, we will talk about basic concepts, the hypercontractive inequality and the KKL theorem. Time permitting, we will discuss the Fourier-Entropy Conjecture and mention some recent progress towards it.

The talk is self-contained and no special background will be assumed.

## An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often non-deterministic pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^eps n}, for all eps > 0.

## Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers

## A p-adic monodromy theorem for de Rham local systems

## Preference Modeling with Context-Dependent Salient Features

## Spectral Independence in High-dimensional Expanders and Applications to the Hardcore Model

## Is the variety of singular tuples of matrices a null cone?

The following multi-determinantal algebraic variety plays an important role in algebra and computational complexity theory: SING_{n,m}, consisting of all m-tuples of n x n complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING_{n,m} will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. <br>

## Learning from Multiple Biased Sources

## Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

We prove that, unconditionally, for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often non-deterministic pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^eps n}, for all eps > 0.