# Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

## From Irreducible Representations to Locally Decodable Codes

Klim Efremenko
Tel Aviv University
May 15, 2012

## Pseudorandomness from Shrinkage

Raghu Meka
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.

## Lower Bounds for Matching Vector Codes

Abhishek Bhowmick
University of Texas at Austin
May 1, 2012

## Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis

Mario Szegedy
Rutgers, The State University of New Jersey
April 30, 2012

## Pseudorandom Generators for Read-Once ACC^0

Srikanth Srinivasan
DIMACS
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

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

Sushant Sachdeva