Computer Science and Discrete Mathematics (CSDM)

Several classical results in Ramsey theory (including famous theorems of Schur, van der Waerden, Rado) deal with finding monochromatic linear patterns in two-colourings of the integers.  Our topic will be quantitative extensions of such results.  A...

A predicate P:Σk→0,1 is said to be linearly embeddable if the set of assignments satisfying it can be embedded in an Abelian group.

In this talk, we will present this notion and mention problems it relates to from various areas. These areas...

Suppose you have a set S of integers from {1 , 2 , … , N} that contains at least N / C elements. Then for large enough N , must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is...

Extremal combinatorics is a central research area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has...

Suppose you have a set S of integers from {1 , 2 , … , N} that contains at least N / C elements. Then for large enough N , must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is...

A central goal of physics is to understand the low-energy solutions of quantum interactions between particles. This talk will focus on the complexity of describing low-energy solutions; I will show that we can construct quantum systems for which the...

Randomness is a vital resource in computation, with many applications in areas such as cryptography, data-structures and algorithm design, sampling, distributed computing, etc. However generating truly random bits is expensive, and most sources in...

In the minimum cost set cover problem, a set system is given as input, and the goal is to find a collection of sets with minimum cost whose union covers the universe. This NP-hard problem has long been known to admit logarithmic approximations...

Robust sublinear expansion represents a fairly weak notion of graph expansion which still retains a number of useful properties of the classical notion. The general idea behind it has been introduced by Komlós and Szemerédi around 25 years ago and...

Suppose we are given matchings M1,....,MN of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of size t...