Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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).

Non-commutative rank

Visu Makam
University of Michigan; Member, School of Mathematics
February 5, 2019

A linear matrix is a matrix whose entries are linear forms in some indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The commutative rank of a linear matrix is obtained by interpreting it as a matrix with entries in the function field $F(t_1,\dots,t_m)$, and is directly related to the central PIT (polynomial identity testing) problem. The

Near-Optimal Strong Dispersers

Dean Doron
The University of Texas at Austin
February 4, 2019

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs. 

PCP and Delegating Computation: A Love Story.

Yael Tauman Kalai
Microsoft Research
January 28, 2019

In this talk, I will give an overview on how PCPs, combined with cryptographic tools,
are used to generate succinct and efficiently verifiable proofs for the correctness of computations.
I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive*
(assuming the existence of public parameters) and are *publicly verifiable*.
In particular, I will focus on a recent result with Omer Paneth and Lisa Yang,
where we show how to construct such proofs for all polynomial time computations,

New Results on Projections

Guy Moshkovitz
Member, School of Mathematics
January 22, 2019

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan number, Sauer-Shelah Lemma, Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for linear k and sub-exponential m. 

Based on joint work with Noga Alon and Noam Solomon.