One of the central problems of coding theory is to determine the
trade-off between the amount of information a code can carry
(captured by its rate) and its robustness to resist message
corruption (captured by its distance). On the existential
side...
Gaussian elimination is one of the oldest and most well-known
algorithms for solving a linear system. In this talk, we give a
basic, yet thorough overview of the algorithm, its variants, and
standard error and conditioning estimates. In addition, a...
Since the late 19th century, mathematicians have realized the
importance and generality of selection problems: given a collection
of sets, select an element in each set, possibly in a ``nice”
way. Of particular importance in computer science is
the...
Training a predictor to minimize a loss function fixed in
advance is the dominant paradigm in machine learning. However, loss
minimization by itself might not guarantee desiderata like fairness
and accuracy that one could reasonably expect from a...
The study of nodal sets, i.e. zero sets of eigenfunctions, on
geometric objects can be traced back to De Vinci, Galileo, Hook,
and Chladni. Today it is a central subject of spectral geometry.
Sturm (1836) showed that the n-th eigenfunction of the...
A nodal domain of a Laplacian eigenvector of a graph is a
maximal connected component where it does not change sign.
Sparse random regular graphs have been proposed as discrete toy
models of "quantum chaos", and it has accordingly been
conjectured...
The absorption method is a very simple yet surprisingly powerful
idea coming from extremal combinatorics which allows one to convert
asymptotic results into exact ones. It has produced a remarkable
number of success stories in recent years with...
Proving a 2009 conjecture of Itai Benjamini, we show: For
any C, there is a greater than 0 such that for any simple random
walk on an n-vertex graph G, the probability that the first Cn
steps of the walk hit every vertex of G is at most
exp[-an]. ...
Two recent and seemingly-unrelated techniques for proving mixing
bounds for Markov chains are:
(i) the framework of Spectral Independence, introduced by Anari,
Liu and Oveis Gharan, and its numerous extensions, which have given
rise to several...
