Random sampling a subgraph of a graph is an important
algorithmic technique. Solving some problems on the (smaller)
subgraph is naturally faster, and can give either a useful
approximate answer, or sometimes even give a result that can be
quickly...
For a fixed integer k > 1, the Boolean k-XOR problem consists
of a system of linear equations mod 2 with each equation involving
exactly k variables. We give an algorithm to strongly refute
*semi-random* instances of the Boolean k-XOR problem on n...
This talk introduces a directed analog of the
classical Laplacian matrix and discusses algorithms for
solving certain problems related to them. Of particular interest is
that using such algorithms, one can compute the stationary
distribution of a...
A subgraph of an edge-coloured graph is called rainbow if all
its edges have distinct colours. The study of rainbow
subgraphs goes back to the work of Euler on Latin squares in the
18th century. Since then rainbow structures were the focus
of...
This talk gives an introduction on how to quickly solve linear
systems where the matrix of the system is the Laplacian matrix of
any undirected graph. No prior familiarity with optimization is
assumed. In the process, we will cover:
We consider the Glauber dynamics (also called Gibbs sampling)
for sampling from a discrete distribution in high-dimensional space
(e.g., selecting a uniformly random legal coloring or independent
set in a given graph, or selecting a "typical" state...
Expander graphs are graphs which simultaneously are both sparse
and highly connected. The theory of expander graphs received a lot
of attention in the past half a century, from both computer science
and mathematics. In recent years, a new theory of...
Valiant (1980) showed that general arithmetic circuits with
negation can be exponentially more powerful than monotone ones. We
give the first qualitative improvement to this classical result: we
construct a family of polynomials P-n in n variables...
Expander graphs are graphs which simultaneously are both sparse
and highly connected. The theory of expander graphs received a
lot of attention in the past half a century, from both computer
science and mathematics. In recent years, a new theory of...
Non-constructive existence proofs, which establish the existence
of objects without furnishing an efficient algorithm to produce
examples, abound in mathematics. How hard is it, computationally,
to find objects whose existence is guaranteed non...
