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