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