# Computer Science and Discrete Mathematics (CSDM)

## Quantum computing with noninteracting particles

## Dimension expanders via rank condensers

## On monotonicity testing and boolean isoperimetric type theorems

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from being monotone with constant probability. Joint work with Dor Minzer and Muli Safra. The paper is available on ECCC: http://eccc.hpi-web.de/report/2015/011/

## Publicly-verifiable non-interactive arguments for delegating computation

## Small value parallel repetition for general games

## More on sum-of-squares proofs for planted clique

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and anyone interested can watch it on https://video.ias.edu/csdm/2014/1125-AviWigderson).

## Area Laws and the Complexity of Quantum States

## Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression

## Parallel Repetition From Fortification

As corollaries, we obtain: