Spring 2017

**Abstract:** We give the first polynomial upper bound on the
mixing time of the edge-flip Markov chain for unbiased dyadic tilings,
resolving an open problem originally posed by Janson, Randall, and
Spencer in 2002. The technique used, adapted from spin system analysis
in statistical physics and not widely used in computer science
literature, involves a multilevel decomposition of the state space and
is of independent interest. A dyadic tiling of size n is a tiling of
the unit square by n non-overlapping dyadic rectangles, each of area
1/n, where a dyadic rectangle is any rectangle that can be written in
the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for
non-negative integers a,b,s,t. The edge-flip Markov chain selects a
random edge of the tiling and replaces it with its perpendicular
bisector if doing so yields a valid dyadic tiling. Specifically, we show
that the relaxation time of the edge-flip Markov chain for dyadic
tilings is at most O(n^{4.09}), which implies that the mixing time is at
most O(n^{5.09}). We complement this by showing that the relaxation
time is at least \Omega(n^{1.38}), improving upon the previously best
lower bound of \Omega(n log n) coming from the diameter of the chain.
This is joint work with David Levin and Alexandre Stauffer.

**Abstract:** We present an algorithm that, with high
probability, generates a random spanning tree
from an edge-weighted undirected graph in O (n^{5/3}m^{1/3}) time.
The tree is sampled from a
distribution where the probability of each tree is proportional to the
product of its edge weights.
This improves upon the previous best algorithm due to Colbourn et al.
that runs in matrix
multiplication time, O(n^\omega). For the special case of unweighted
graphs, this improves upon the
best previously known running time of ˜O(min{n^\omega, mn^{1/2},
m^{4/3}}) for m >> n^{7/4} (Colbourn et al. ’96, Kelner-Madry ’09,
Madry et al. ’15).
The effective resistance metric is essential to our algorithm, as in
the work of Madry et al., but
we eschew determinant-based and random walk-based techniques used by
previous algorithms.
Instead, our algorithm is based on Gaussian elimination, and the fact
that effective resistance is
preserved in the graph resulting from eliminating a subset of
vertices (called a Schur complement).

As part of our algorithm, we show how to compute -approximate effective resistances for a set S of vertex pairs via approximate Schur complements in O (m + (n + |S|)/\eps^{ −2}) time, without using the Johnson-Lindenstrauss lemma which requires eO(min{(m+|S|) \eps{−2},m+n /eps^{−4} +|S|/eps^{ −2}}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn’t sufficiently accurate.

Joint work with Rasmus Kyng, John Peebles, Anup Rao, and Sushant Sachdeva**Abstract:** Spielman and Teng (2004) showed that linear
systems in Laplacian matrices can be solved in nearly linear time. Since
then, a major research goal has been to develop fast solvers for linear
systems in other classes of matrices. Recently, this has led to fast
solvers for directed Laplacians (CKPPRSV'17) and connection Laplacians
(KLPSS'16).

Connection Laplacians are a special case of PSD-Graph-Structured Block Matrices (PGSBMs), block matrices whose non-zero structure correspond to a graph, and which additionally can be expressed as a sum of positive semi-definite matrices each corresponding to an edge in the graph.

A major open question is whether fast solvers can be obtained for all PGSBMs (Spielman, 2016). Fast solvers for Connection Laplacians provided some hope for this. Other important families of matrices in the PGSBM class include truss stiffness matrices, which have many applications in engineering, and multi-commodity Laplacians, which arise when solving multi-commodity flow problems.

In this talk, we show that multi-commodity and truss linear systems are unlikely to be solvable in nearly linear time, unless general linear systems (with integral coefficients) can be solved in nearly linear time. Joint work with Rasmus Kyng.

**Abstract:** Optimization problems arising in
decentralized multi-agent systems have gained significant attention in
the context of cyber-physical, communication, power, and robotic
networks combined with privacy preservation, distributed data mining and
processing issues. The distributed nature of the problems is inherent
due to partial knowledge of the problem data (i.e., a portion of the
cost function or a subset of the constraints is known to different
entities in the system), which necessitates costly communications among
neighboring agents. In this talk, we present a new class of
decentralized first-order methods for nonsmooth and stochastic
optimization problems which can significantly reduce the number of
inter-node communications. Our major contribution is the development of
decentralized communication sliding methods, which can skip inter-node
communications while agents solve the primal subproblems iteratively
through linearizations of their local objective functions.

**Abstract:** In this talk we will show that, among real
polynomials which are invariant under the action of a finite reflection
group, a large family of them, either low degree or sparse, are globally
nonnegative provided they are nonnegative on the hyperplane arrangement
(our test set) associated to the reflection group. We explore stronger
conditions on the degree and the sparsity that reduce the size of the
test set, as it happens for the particular case of symmetric
polynomials.

**Abstract:** We study stable marriage where individuals
strategically submit private preference information to a publicly known
stable marriage algorithm. We prove that no stable marriage algorithm
ensures actual stability at every Nash equilibrium when individuals are
strategic. More specifically, we show that any rational marriage, stable
or otherwise, can be obtained at a Nash equilibrium. Thus the set of
Nash equilibria provides no predictive value nor guidance for mechanism
design. We propose the following new minimal dishonesty equilibrium
refinement, supported by experimental economics results: an individual
will not strategically submit preference list L if there exists a more
honest L' that yields as preferred an outcome. Then for all marriage
algorithms satisfying monotonicity and IIA, every minimally dishonest
equilibrium yields a sincerely stable marriage. This result supports the
use of algorithms less biased than the (Gale-Shapley) man-optimal,
which we prove yields the woman-optimal marriage in every minimally
dishonest equilibrium. However, bias cannot be totally eliminated, in
the sense that no monotonic IIA stable marriage algorithm is certain to
yield the egalitarian-optimal marriage in a minimally dishonest
equilibrium – thus answering a 28-year old open question of Gusfield and
Irving's in the negative. Finally, we show that these results extend to
student placement problems, where women are polygamous and honest, but
not to admissions problems, where women are both polygamous and
strategic.

Based on joint work with Craig Tovey at Georgia Tech.

**Abstract:** The concentration of measure phenomenon is of
great importance in probabilistic combinatorics and theoretical computer
science. For example, in the theory of random graphs, we are often
interested in showing that certain random variables are concentrated
around their expected values. In this talk we consider a variation of
this theme, where we are interested in proving that certain random
variables remain concentrated around their expected trajectories as an
underlying random process (or random algorithm) evolves.

In particular, we shall give a gentle introduction to the differential equation method popularized by Wormald, which allows for proving such dynamic concentration results. This method systematically relates the evolution of a given random process with an associated system of differential equations, and the basic idea is that the solution of the differential equations can be used to approximate the dynamics of the random process.

If time permits, we shall also sketch a new simple proof of Wormalds method.

**Abstract:** Beginning with Szemeredi’s regularity lemma,
the theory of graph decomposition and graph limits has greatly increased
our understanding of large dense graphs and provided a framework for
graph approximation. Unfortunately, much of this work does not
meaningfully extend to non-dense graphs. We present preliminary work
towards our goal of creating tools for approximating graphs of
intermediate degree (average degree o(n) and not bounded). We give a new
random graph model that produces a graph of desired size and density
that approximates the number of small closed walks of a given sparse
graph (i.e., small moments of its eigenspectrum). We show how our model
can be applied to approximate the hypercube graph. This is joint work
with Santosh Vempala.

**Abstract:**The random to random shuffle on a deck of cards
is given by at each step choosing a random card from the deck, removing
it, and replacing it in a random location. We show an upper bound for
the total variation mixing time of the walk of 3/4n log(n) +cn steps.
Together with matching lower bound of Subag (2013), this shows the walk
mixes with cutoff at 3/4n log(n) steps, answering a conjecture of
Diaconis. We use the diagonalization of the walk by Dieker and Saliola
(2015), which relates the eigenvalues to Young tableaux.

Joint work with Evita Nestoridi