Recently Added

Bypassing UGC From Some Optimal Geometric Inapproximability Results

Rishi Saket
Princeton University
February 8, 2011

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In our work we bypass the UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. This talk shall focus on one of the problems as described below.

Local Testing and Decoding of Sparse Linear Codes

Shubhangi Saraf
Massachusetts Institute of Technology
February 22, 2011

We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and interesting classes of distributions, and use this to show local testability for the corresponding codes.

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.

Some Equations and Games in Evolutionary Biology

Christine Taylor
Harvard University; Member, School of Mathematics
February 14, 2011

The basic ingredients of Darwinian evolution, selection and mutation, are very well described by simple mathematical models. In 1973, John Maynard Smith linked game theory with evolutionary processes through the concept of evolutionarily stable strategy. Since then, cooperation has become the third fundamental pillar of evolution. I will discuss, with examples from evolutionary biology and ecology, the roles played by replicator equations (deterministic and stochastic) and cooperative dilemma games in our understanding of evolution.