Computer Science and Discrete Mathematics (CSDM)

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space  complexity as it constitutes the main route...

We prove the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility...

Erdős' unit distance problem and his related distinct distances problem are arguably the best known open problems in discrete geometry.

They ask for the maximum possible number of unit distances, and the minimum possible number of distinct...

The Lipschitz extension problem is the following basic “meta question” in metric geometry:  Suppose that X and Y are metric spaces and A is a subset of X. What is the smallest K such that every Lipschitz function f:A\to Y has an extension F:X\to Y...

A CSS quantum code C=(W1,W2) is a pair of orthogonal subspaces in 𝔽n2. The distance of C is the smallest hamming weight of a vector in W⊥1−W2 or W⊥2−W1. A large distance roughly means that the quantum code can correct many errors that affect the...

If f is a real polynomial and A and B are finite sets of cardinality n, then Elekes and Ronyai proved that either f(A×B) is much larger than n, or f has a very specific form (essentially, f(x,y)=x+y). In the talk I will tell about an analogue of...

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