## Fast Random Projections

## Edward T. Cone Concert Talk

Listen to members of the string quartet Brooklyn Rider discuss music with Institute Artist-in-Residence Derek Bermel.

## Generalized Kepler Problems

ANALYSIS/MATHEMATICAL PHYSICS SEMINAR

## THE IWASAWA MAIN CONJECTURE FOR GL(2) MINI-COURSE

## Automorphy Lifting for Galois Representations With Small Residual Image

**GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR**

## IWASAWA: Lecture 1

## Randomness in Number Theory

## 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).

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

SPECIAL LECTURE IN GEOMETRY/TOPOLOGY