School of Mathematics
Formal Abstract Homotopy Theory
Semantics of Higher Inductive Types
Derandomizing BPL?
I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll see why each falls short of complete derandomization, BPL=L, hopefully motivating further work on this basic problem.
Collective Phenomena, Collective Motion, and Collective Action in Ecological Systems
Fundamental questions in basic and applied ecology alike involve complex adaptive systems, in which localized interactions among individual agents give rise to emergent patterns that feed back to affect individual behavior.
Polar Codes and Randomness Extraction for Structured Sources
Polar codes have recently emerged as a new class of low-complexity codes achieving Shannon capacity. This talk introduces polar codes with emphasis on the probabilistic phenomenon underlying the code construction. New results and connections to randomness extraction for structured sources are discussed.
pi_2(s^2) in HoTT
New Approximations of the Total Variation, and Filters in Image Processing
I will present new results concerning the approximation of the BV-norm by nonlocal, nonconvex, functionals. The original motivation comes from Image Processing. Numerous problems remain open. The talk is based on a joint work with H.-M. Nguyen.
The Chasm at Depth 3
I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit over the complex numbers, can be also computed by a *depth 3* arithmetic circuit of size sub exponential in d; specifically size 2^{sqrt d polylog n} (the actual paper gives a more precise bound depen