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...
A polynomial with nonnegative coefficients is strongly
log-concave if it and all of its derivatives are log-concave as
functions on the positive orthant. This rich class of polynomials
includes many interesting examples, such as homogeneous real...
Establishing inequalities among graph densities is a central
pursuit in extremal graph theory. One way to certify the
nonnegativity of a graph density expression is to write it as a sum
of squares or as a rational sum of squares. In this talk, we...
A polynomial with nonnegative coefficients is strongly
log-concave if it and all of its derivatives are log-concave as
functions on the positive orthant. This rich class of polynomials
includes many interesting examples, such as homogeneous real...
"Games against Nature" [Papadimitriou '85] are two-player games
of perfect information, in which one player's moves are made
randomly. Estimating the value of such games (i.e., winning
probability under optimal play by the strategic player) is
an...
