# School of Mathematics

## Workshop on Topology: Identifying Order in Complex Systems

## Fundamental Groups of Random Simplicial Complexes

## Hardness Escalation and the Rank of Polynomial Threshold Proofs

## The Permanents of Gaussian Matrices

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial hierarchy collapses. Several optics groups are already working toward doing our experiment.

## (Some) Generic Properties of (Some) Infinite Groups

This talk will be a biased survey of recent work on various properties of elements of infinite groups, which can be shown to hold with high probability once the elements are sampled from a large enough subset of the group (examples of groups: linear groups over the integers, free groups, hyperbolic groups, mapping class groups, automorphism groups of free groups . . . )

## Self-Correction, Distance Estimation and Local Testing of Codes

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries:

1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword $c$, and an index $i\in [n]$ to correct, with high probability over $i$ and over the internal randomness, the local algorithm returns a list of possible corrections that contains $c_i$.

## Combinatorial Theorems in Random Sets

## Planar Convexity, Infinite Perfect Graphs and Lipschitz Continuity

Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions - e.g. the class of Lipschitz continuous functions - and to meta-mathematical properties of sub-ideals of the meager ideal (the sigma-ideal generated by nowhere dense sets over a Polish space) which reduce to finite Ramsey-type relations between random graphs and perfect graphs.

## A Rigorous Renormalization Group Study of a p-Adic Quantum Field Theory

ANALYSIS/MATHEMATICAL PHYSICS SEMINAR