# Computer Science and Discrete Mathematics (CSDM)

## Sunflowers and friends

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

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

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

## X-Ramanujan graphs: ex uno plures

## 2-universality of random graphs.

## Small-Set Expansion on the Grassmann Graph.

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.

## Asymptotic spectra and their applications II

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.

## Breaking the Circuit-Size Barrier in Secret Sharing

Based on joint work with Tianren Liu and Hoeteck Wee.

## Asymptotic spectra and their applications I

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.