# Computer Science and Discrete Mathematics (CSDM)

## Thresholds Versus Fractional Expectation-Thresholds

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 historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area.

## Graph Sparsification via Short Cycle Decomposition

## Regularity lemma and its applications Part I

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 of the talk covers some basic knowledge about the regularity lemma and some of its applications, such as the graph removal lemma. I will also discuss some recent works related to the removal lemma.

## Rainbow fractional matchings

## Constraint Satisfaction Problems and Probabilistic Combinatorics II

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 deep connections to statistical physics.

In this second talk of the series, I'll cover some results regarding random constraint satisfaction problems and their connection to statistical physics.

## Lifting small locally testable codes (LTCs) to large LTCs via HDXs

## Constraint Satisfaction Problems and Probabilistic Combinatorics I

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 deep connections to statistical physics.

## An isoperimetric inequality for the Hamming cube and some consequences

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 cubes, and later by Ellis for subsets of any size. Our inequality also plays a key role in a recent result on the asymptotic number of maximal independent sets in the cube.

This is joint work with Jeff Kahn.

## Extremal set theory II

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 recent progress in the Erdos Matching Conjecture, which suggests the largest size of a family of k-subsets of an n-element set with no s pairwise disjoint sets.