Computer Science and Discrete Mathematics (CSDM)

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to...

Given an increasing family F in {0,1}^n, its measure according to mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. Thresholds of families have been of great...

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple...

Szemeredi's regularity lemma is an important tool in modern graph theory. It and its variants have numerous applications in graph theory, which in turn has applications in fields such as theoretical computer science and number theory. The first part...

Given a family of m matchings in a graph G (where each matching can be thought of as a color class), a rainbow matching is a choice of edges of distinct colors that forms a matching. How many matchings of size n are needed to guarantee the existence...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

In this talk, I'll illustrate how to lift a "small" locally testable code via a high dimensional expander (HDX) to a "large" locally testable code. Given a D-left regular bipartite graph G = ([n], [m], E) and a "small" code C \in {0,1}^D, the Tanner...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a “stability” version of Harper’s edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half...

Extremal set theory typically asks for the largest collection of sets satisfying certain constraints. In the first talk of these series, I'll cover some of the classical results and methods in extremal set theory. In particular, I'll cover the...