Computer Science and Discrete Mathematics (CSDM)

The "cap set problem" asks for the size of the largest subset $S$ of the vector space $\mathbb F_3^n$ containing no three elements summing to 0. Progress on this problem was slow for many years, until the spring of 2016, when a very short argument...

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance of a constraint satisfaction problem (CSP(P)) where each of the $\Delta n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at random is unsatisfiable with...

The motivating question for this talk is: What does a sparse Erdős–Rényi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo...

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size...

Consider a set of $n$ points in $\mathbb R^d$. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. Let us call such a line an "ordinary line". In a...

In this talk I will review some of the classical (and fundamental) results in the theory of graph rigidity.

The stochastic block model (SBM) is a random graph model with planted clusters. It has been popular to model unsupervised learning problems, inhomogeneous random graphs and to study statistical versus computational tradeoffs. This talk overviews the...

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient...

The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic...

Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography...