# Computer Science and Discrete Mathematics (CSDM)

## Collective Coin-Flipping Protocols and Influences of Coalitions

## Fooling polytopes

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program. Joint work with Ryan O'Donnell and Rocco Servedio.

## Factors of sparse polynomials: structural results and some algorithms

In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.

## On the Approximation Resistance of Balanced Linear Threshold Functions

## A Brief Tour of Proof Complexity: Lower Bounds and Open Problems

I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited two-player games. I will also define algebraic and semi-algebraic systems (SOS, IPS, Polynomial Calculus).

## An Application of the Universality Theorem for Tverberg Partitions

We show that, as a consequence of a remarkable new result of

Attila P\'or on universal Tverberg partitions, any large-enough set

$P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point

has half-space depth at least $c_d \cdot |P|$, where $c_d \in (0, 1)$

depends only on $d$. We then give an application of this result to

computing weak $\eps$-nets by random sampling. Joint work with Nabil

Mustafa.

## Halting problems for sandpiles and abelian networks

Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex with at least as many chips as out-neighbors, and send one chip from that vertex to each of its out-neighbors. Repeat, until there is no such vertex.

## Near log-convexity of measured heat in (discrete) time and consequences

We answer a 1982 conjecture of Erdős and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of the $k$-Hamming distance is $\Omega(k \log k)$ and that consequently any property tester for k-linearity requires $\Omega(k \log k)$.

## Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes

I will talk about a recent result showing that some well-studied polynomial-based error-correcting codes

(Folded Reed-Solomon Codes and Multiplicity Codes) are "list-decodable upto capacity with constant

list-size".

At its core, this is a statement about questions of the form: "Given some points in the plane,

how many low degree univariate polynomials are such that their graphs pass through 10% of these points"?

This leads to list-decodable and locally list-decodable error-correcting codes with the best known parameters.