Fall 2016

**Abstract:** I will present work on a new application of
Markov chains to distributed computing. Motivated by programmable matter
and the behavior of biological distributed systems such as ant
colonies, the geometric amoebot model abstracts these processes as
self-organizing particle systems where particles with limited
computational power move on the triangular lattice. Previous algorithms
developed in this setting have relied heavily on leader election, tree
structures that are not robust to failures, and persistent memory. We
developed a distributed algorithm for the compression problem, where all
particles want to gather together as tightly as possible, that is based
on a Markov chain and is simple, robust, and oblivious. Tools from
Markov chain analysis enable rigorous proofs about its behavior, and we
show compression will occur with high probability. This joint work with
Joshua J. Daymude, Dana Randall, and Andrea Richa appeared at PODC 2016.
I will also present some more recent extensions of this approach to
other problems, which is joint work with Marta Andres Arroyo as well.

**Abstract:** Parallel algorithms study ways of speeding up
sequential algorithms by splitting work onto multiple processors.
Theoretical studies of parallel algorithms often focus on performing a
small number of operations, but assume more generous models of
communication.
Recent progresses led to parallel algorithms for many graph optimization
problems that have proven to be difficult to parallelize. In this talk I
will survey routines at the core of these results: low diameter
decompositions, random sampling, and iterative methods.

**Abstract:** Graded posets are partially ordered sets
equipped with a unique rank function that respects the partial order and
such that neighboring elements in the Hasse diagram have ranks that
differ by one. We frequently find them throughout combinatorics,
including the canonical partial order on Young diagrams and plane
partitions, where their respective rank functions are the area and
volume under the configuration. We ask when it is possible to
efficiently sample elements with a fixed rank in a graded poset. We show
that for certain classes of posets, a biased Markov chain that connects
elements in the Hasse diagram allows us to approximately generate
samples from any fixed rank in expected polynomial time. While varying a
bias parameter to increase the likelihood of a sample of a desired size
is common in statistical physics, one typically needs properties such
as log-concavity in the number of elements of each size to generate
desired samples with sufficiently high probability. Here we do not even
require unimodality in order to guarantee that the algorithm succeeds in
generating samples of the desired rank efficiently. This joint work
with Prateek Bhakta, Ben Cousins, and Dana Randall will appear at SODA
2017.

**Abstract:** We consider the problem of estimating the
mean and covariance of a distribution from iid samples in R^n in the
presence of an η fraction of malicious noise; this is in contrast to
much recent work where the noise itself is assumed to be from a
distribution of known type. This agnostic learning problem includes many
interesting special cases, e.g., learning the parameters of a single
Gaussian (or finding the best-fit Gaussian) when η fraction of data is
adversarially corrupted, agnostically learning a mixture of Gaussians,
agnostic ICA, etc. We present polynomial-time algorithms to estimate the
mean and covariance with error guarantees in terms of
information-theoretic lower bounds. We also give an agnostic algorithm
for estimating the 2-norm of the covariance matrix of a Gaussian. This
joint work with Santosh Vempala and Anup Rao appeared in FOCS 2016.

**Abstract:** We study the cost function for hierarchical
clusterings introduced by Dasgupta where hierarchies are treated as
first-class objects rather than deriving their cost from projections
into flat clusters. It was also shown that a top-down algorithm returns a
hierarchical clustering of cost at most O (α_n log n) times the cost of
the optimal hierarchical clustering, where α_n is the approximation
ratio of the Sparsest Cut subroutine used. Thus using the best known
approximation algorithm for Sparsest Cut due to Arora-Rao-Vazirani, the
top down algorithm returns a hierarchical clustering of cost at most
O(log^{3/2} n) times the cost of the optimal solution. We improve this
by giving an O(log n)- approximation algorithm for this problem. Our
main technical ingredients are a combinatorial characterization of
ultrametrics induced by this cost function, deriving an Integer Linear
Programming (ILP) formulation for this family of ultrametrics, and
showing how to iteratively round an LP relaxation of this formulation by
using the idea of sphere growing which has been extensively used in the
context of graph partitioning. We also prove that our algorithm returns
an O(log n)-approximate hierarchical clustering for a generalization of
this cost function also studied in Dasgupta. This joint work with
Sebastian Pokutta is to appear in NIPS 2016 (oral presentation).

**Abstract:**The Jacobian (or sandpile group) of a graph is
a well-studied group associated to the graph, known to biject with the
set of spanning trees of the graph via a number of classical
combinatorial mappings. The algebraic definition of a Jacobian extends
to regular matroids, but without the notion of vertices, many such
combinatorial bijections fail to generalize. In this talk, I will
discuss how orientations provide a way to overcome such obstacle. We
give a novel, effectively computable bijection scheme between the
Jacobian and the set of bases of a regular matroid, in which polyhedral
geometry plays an important role; along the way we also obtain new
enumerative results related to the Tutte polynomial. This is joint work
with Spencer Backman and Matt Baker.

**Abstract:** At the intersection of computability and
algebraic geometry, the following question arises: does an integral
polynomial system of equations have any integral solutions? Famously,
the combined work of Robinson, Davis, Putnam, and Matiyasevich answers
this in the negative. Nonetheless, algorithms have played in increasing
role in the development of algebraic geometry and its many applications.
I address some research related to this general theme and some
outstanding questions.

**Abstract:** Conditional gradient algorithms (also often called
Frank-Wolfe algorithms) are popular due to their simplicity of only
requiring a linear optimization oracle and more recently they also
gained significant traction for online learning. While simple in
principle, in many cases the actual implementation of the linear
optimization oracle is costly. We show a general method to lazify
various conditional gradient algorithms, which in actual computations
leads to several orders of magnitude of speedup in wall-clock time. This
is achieved by using a faster separation oracle instead of a linear
optimization oracle, relying only on few linear optimization oracle
calls.