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

## Topological Analysis of Grain Boundaries

GEOMETRY AND CELL COMPLEXES

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

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

## CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

## Members Seminar: Linear Equations in Primes and Nilpotent Groups

## Periodic Bounce Orbits of Prescribed Energy

GEOMETRY/DYNAMICAL SYSTEMS

Periodic bounce orbits are generalizations of billiard trajectories in the presence of a potential. Using an approximation technique by Benci-Giannoni we prove existence of periodic bounce orbits of prescribed energy. At the end of the talk I will sketch very recent work in which we allow much more general Lagrangian systems including magnetic and Finsler billiards.

This is joint work with Marco Mazzucchelli.

## Learning with Boolean Threshold Functions, a Statistical Physics Perspective

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered systems to characterize BTF in a quantitative way [1], with an emphasis on computational and geometrical aspects. These techniques will be illustrated on two particular cases: the celebrated perceptron (Linear Threshold Function) [2], and the more realistic tempotron model of a neuron [3,4].