# Computer Science and Discrete Mathematics (CSDM)

## Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei)

## General strong polarization

## Geometric complexity theory from a combinatorial viewpoint

## Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound

## A practical guide to deep learning

## Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity II

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object interacts with a class of tests, and to approximately determine the outcome of these tests.

## Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity I

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object interacts with a class of tests, and to approximately determine the outcome of these tests.

## Pseudorandom generators for unordered branching programs

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman where they required seed length $n^{1/2+o(1)}$.

## Language edit distance, $(\min,+)$-matrix multiplication & beyond

The language edit distance is a significant generalization of two basic problems in computer science: parsing and string edit distance computation. Given any context free grammar, it computes the minimum number of insertions, deletions and substitutions required to convert a given input string into a valid member of the language. In 1972, Aho and Peterson gave a dynamic programming algorithm that solves this problem in time cubic in the string length. Despite its vast number of applications, in forty years there has been no improvement over this running time.