2022-2023 Seminars

In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this...

In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as...

Let C be a class of metric spaces. We consider the following computational metric embedding problem: given a vector x in R^{n choose 2} representing pairwise distances between n points, change the minimum number of entries of x to ensure that the...

A finite set system is union-closed if for every pair of sets in the system their union is also in the system.  Frankl in 1979 conjectured that for any such system there exists an element which is contained in ½ of the sets in that system (the only...

Discrepancy theory provides a powerful approach to improve upon the bounds obtained by a basic application of the probabilistic method. In recent years, several algorithmic approaches have been developed for various classical results in the area. In...

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 $\mathcal{C} = (W_1, W_2)$ is a pair of orthogonal subspaces in $\mathbb{F}_2^n$. The distance of $\mathcal{C}$ is the smallest hamming weight of a vector in $W_1^{\perp}-W_2$ or $W_2^{\perp}-W_1$. A large distance roughly means...