# Computer Science and Discrete Mathematics (CSDM)

## Pseudorandomness from Shrinkage

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

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

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

## Pseudorandom Generators for Read-Once ACC^0

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

## Nondeterministic Property Testing

## Near-Linear Time Approximation Algorithm for Balanced Separator

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

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.