Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Pseudorandomness from Shrinkage

Raghu Meka
Institute for Advanced Study
May 8, 2012

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we only know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can indeed construct PRGs which are essentially best possible without in turn improving the lower bounds.

Topology of Norms Defined by Systems of Linear forms

Pooya Hatami
University of Chicago
May 7, 2012

Gowers' uniformity norms are defined by average of a function over specific sets of linear forms. We study norms that are similarly defined by a system of linear forms. We prove that for bounded complex functions over $F_p^n$, each such norm is equivalent to a Gowers' uniformity norm. To do this we prove direct and inverse theorems for norms defined by a system of linear forms.

Joint work with Shachar Lovett.

Pseudorandom Generators for Read-Once ACC^0

Srikanth Srinivasan
April 24, 2012

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and generalized modulo m gates, where m is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.

Joint work with Dmitry Gavinsky (NEC Labs) and Shachar Lovett (IAS).

Computational Entropy

Salil Vadhan
Harvard University; Visiting Researcher Microsoft Research SVC; Visiting Scholar Stanford University
April 23, 2012

Nondeterministic Property Testing

Laszlo Lovasz
Eotvos Lorand University, Budapest; Member, School of Mathematics
April 17, 2012

Near-Linear Time Approximation Algorithm for Balanced Separator

Sushant Sachdeva
Institute for Advanced Study
April 16, 2012

The goal of the Balanced Separator problem is to find a balanced cut in a given graph G(V,E), while minimizing the number of edges that cross the cut. It is a fundamental problem with applications in clustering, image segmentation, community detection, and as a primitive for divide-and-conquer on graphs.

List-Decoding Multiplicity Codes

Swastik Kopparty
Rutgers University
April 10, 2012

We study the list-decodability of multiplicity codes.
These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching 1 while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction of errors.