Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Sunflowers and friends

Shachar Lovett
University of California San Diego
November 5, 2018
The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other combinatorial structures, such as randomness extractors, intersecting families and DNFs.

Based on joint works with Xin Li, Noam Solomon and Jiapeng Zhang.

On the NP-hardness of 2-to-2 Games

Dor Minzer
Member, School of Mathematics
October 30, 2018

The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems. 

We will discuss PCPs, the Unique-Games Conjecture and some recent progress. (no familiarity with PCPs or with last week's talk are needed).

 

Small-Set Expansion on the Grassmann Graph.

Dor Minzer
Member, School of Mathematics
October 23, 2018
A graph G is called a small set expander if any small set of vertices contains only a small fraction of the edges adjacent to it.
This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was motivated by recent applications to Probabilistically Checkable Proofs and hardness of approximation.

Approximating the edit distance to within a constant factor in truly subquadratic time.

Mike Saks
Rutgers University
October 22, 2018
Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a classical dynamic programming algorithm that runs in quadratic time.

Asymptotic spectra and their applications II

Jeroen Zuiddam
Member, School of Mathematics
October 16, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.

Asymptotic spectra and their applications I

Jeroen Zuiddam
Member, School of Mathematics
October 9, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.