School of Mathematics

On The Complexity of Computing Roots and Residuosity Over Finite Fields

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

Sparsifying and Derandomizing the Johnson-Lindenstrauss Transform

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.

Members Seminar: Linear Equations in Primes and Nilpotent Groups

Tamar Ziegler
Technion--Israel Institute of Technology
January 30, 2011
A classical theorem of Dirichlet establishes the existence of infinitely many primes in arithmetic progressions, so long as there are no local obstructions. In 2006 Green and Tao set up a program for proving a vast generalization of this theorem. They conjectured a relation between the existence of linear patterns in primes and dynamics on nilmanifolds. In recent joint work with Green and Tao we completed the final step of this program.

CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

Santosh Vempala
Georgia Institute of Technology
January 30, 2011
Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming.