## Generalized Kepler Problems

ANALYSIS/MATHEMATICAL PHYSICS SEMINAR

Guowu Meng

Hong Kong University of Science & Technology; Joint Member, School of Mathematics & Natural Sciences

February 4, 2011

ANALYSIS/MATHEMATICAL PHYSICS SEMINAR

Institute for Advanced Study

February 3, 2011

Jack Thorne

Harvard University

February 3, 2011

**GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR**

Christopher Skinner

Princeton University; Member, School of Mathematics

February 3, 2011

Peter Sarnak

Professor, School of Mathematics

February 2, 2011

Pierre Schapira

University of Paris 6, France

February 1, 2011

SPECIAL LECTURE IN GEOMETRY/TOPOLOGY

Swastik Kopparty

Member, School of Mathematics

February 1, 2011

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

Srikanth Patala

Masachusetts Institute of Technology

February 1, 2011

GEOMETRY AND CELL COMPLEXES

Pierre Schapira

University of Paris 6, France

January 31, 2011

Jelani Nelson

Massachusetts Institute of Technology

January 31, 2011

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.