Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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

Toniann Pitassi
University of Toronto; Visiting Professor, School of Mathematics
March 19, 2019

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

Imre Barany
Renyi Institute, Hungary and UCL, London
March 18, 2019

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

Lionel Levine
Cornell University; von Neumann Fellow
March 12, 2019

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

Mert Saglam
University of Washington
March 11, 2019

We answer a 1982 conjecture of Erd&‌#337;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

Swastik Kopparty
Rutgers University; Member, School of Mathematics
March 5, 2019

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. 

Local and global expansion of graphs

Yuval Peled
New York University
March 4, 2019

The emerging theory of High-Dimensional Expansion suggests a number of inherently different notions to quantify expansion of simplicial complexes. We will talk about the notion of local spectral expansion, that plays a key role in recent advances in PCP theory, coding theory and counting complexity. Our focus is on bounded-degree complexes, where the problems can be stated in a graph-theoretic language: 

Local and global expansion of graphs

Yuval Peled
New York University
March 4, 2019

The emerging theory of High-Dimensional Expansion suggests a number of inherently different notions to quantify expansion of simplicial complexes. We will talk about the notion of local spectral expansion, that plays a key role in recent advances in PCP theory, coding theory and counting complexity. Our focus is on bounded-degree complexes, where the problems can be stated in a graph-theoretic language: 

Strongly log concave polynomials, high dimensional simplicial complexes, and an FPRAS for counting Bases of Matroids

Shayan Oveis Gharan
University of Washington
February 25, 2019

A matroid is an abstract combinatorial object which generalizes the notions of spanning trees,
and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique
to approximately count the number of bases of any given matroid. 

The proof is based on a new connections between high dimensional simplicial complexes, and a new class
of multivariate polynomials called completely log-concave polynomials. In particular, we exploit a fundamental fact from our

Lorentzian polynomials

June Huh
Visiting Professor, School of Mathematics
February 19, 2019

Lorentzian polynomials link continuous convex analysis and discrete convex analysis via tropical geometry. The class of Lorentzian polynomials contains homogeneous stable polynomials as well as volume polynomials of convex bodies and projective varieties. I will give several combinatorial applications. No specific background will be needed to enjoy the talk. Joint work with Petter Brändén (https://arxiv.org/abs/1902.03719).