# School of Mathematics

## Automorphy Lifting for Galois Representations With Small Residual Image

**GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR**

## Randomness in Number Theory

## Topological Analysis of Grain Boundaries

GEOMETRY AND CELL COMPLEXES

## Microlocal Theory of Sheaves and Applications to Non-Displaceability II

SPECIAL LECTURE IN GEOMETRY/TOPOLOGY

## On The Complexity of Computing Roots and Residuosity Over Finite Fields

We study the complexity of computing some basic arithmetic operations over GF(2^n), namely computing q-th root and q-th residuosity, by constant depth arithmetic circuits over GF(2) (also known as AC^0(parity)). Our main result is that these operations require exponential size circuits.

We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over GF(2) can correctly compute the cubic residue symbol for more than 1/3 + o(1) fraction of the elements of GF(2^n).

## Sparsifying and Derandomizing the Johnson-Lindenstrauss Transform

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0<eps<1/2, there exists an embedding into k = O(eps^{-2} * log n) dimensional Euclidean space so that all pairwise distances are preserved up to a 1+eps factor. This lemma has applications in high-dimensional computational geometry (decreasing dimension makes many algorithms run faster), compressed sensing, and numerical linear algebra.