Fall 2014

**Abstract**: In a recent series of papers a surprisingly strong
connection was discovered between standard models of evolution in
mathematical biology and Multiplicative Weights Updates Algorithm, a
ubiquitous model of online learning and optimization. These papers
establish that mathematical models of biological evolution are
tantamount to applying discrete Multiplicative Weights Updates
Algorithm, a close variant of MWUA, on coordination games. We show that
in the case of coordination games, under minimal genericity assumptions,
discrete MWUA (discrete replicator dynamics) converges to pure Nash
equilibria for all but a zero measure of initial conditions. This result
holds despite the fact that mixed Nash equilibria can be exponentially
(or even uncountably) many, completely dominating in number the set of
pure Nash equilibria. As a result mathematical models of haploid
evolution imply the extinction of genetic diversity in the long term
limit.

This is joint work with Ruta Mehta and Georgios Piliouras

**Abstract:** Erdos and Szemeredi conjectured that for any set of
reals, either the sumset or the product set must be near its maximum
size. They also conjectured a multifold version in which one considers
the h-fold sumset and h-fold product set. While resolution of either
conjecture is currently out of reach, significant progress has been made
on weaker forms of these conjectures. In particular, one can force
some structure on the set by assuming the product set is very small in
order to show that the h-fold sumset is indeed very large in this case.
In this talk, we will discuss recent progress on this form of the
conjecture by myself and Ernie Croot.

**Abstract:** Given a family of ideals which are symmetric under
some group action on the variables, a natural question to ask is whether
the generating set stabilizes up to symmetry as the number of variables
tends to infinity. We answer this in the affirmative for a broad class
of toric ideals, settling several open questions coming from algebraic
statistics. Our approach involves factoring an equivariant monomial map
into a part for which we have an explicit degree bound of the kernel,
and a part for which we can prove that the source, a so-called matching
monoid, is equivariantly Noetherian. The proof is mostly combinatorial,
making use of the theory of well-partial orders and its relationship to
Noetherianity of monoid rings. Joint work with Jan Draisma, Rob
Eggermont, and Anton Leykin.

**Abstract:** Optimizing a submodular objective function is a
well studied and important problem and while it is in general NP-hard to
maximize a given objective function, there exist approximation
algorithms with provable guarantees in many settings (unconstrained,
rank constraints, matroid constraints, etc.). In this talk we'll
describe a decentralized model of submodular maximization and will adapt
centralized approximation algorithms to this distributed setting. This
talk is on ongoing work with Nina Balcan.

**Abstract:** The expander mixing lemma relates the combinatorial
expansion of a graph to the spectrum of its adjacency matrix. An
interesting problem is to generalize these concepts to uniform
hypergraphs. In this talk I will discuss recent work generalizing the
inverse mixing lemma of Bilu and Linial for two notions of expansion in
hypergraphs. This is joint work with Emma Cohen, Dhruv Mubayi, and
Prasad Tetali.

**Abstract:** We show FIXP-hardness of computing equilibria in
Arrow-Debreu exchange markets under Leontief utility functions, and
Arrow-Debreu markets under linear utility functions and Leontief
production, thereby settling open questions of Vazirani and Yannakakis
(2009). In both cases, as required under FIXP, the set of instances
mapped onto will admit equilibria, i.e., will be ``yes'' instances. If
all instances are under consideration, then in both cases we prove that
the problem of deciding if a given instance admits an equilibrium is
ETR-complete, where ETR is the class Existential Theory of Reals.
The main technical part of our result is the following reduction: Given a
set 'F' of simultaneous multivariate polynomial equations in which the
variables are constrained to be in a closed bounded region in the
positive orthant, we construct a Leontief market 'M' which has one good
corresponding to each variable in 'F'. We prove that the equilibria of
'M', when projected onto prices of these latter goods, are in one-to-one
correspondence with the set of solutions of the polynomials.
Based on a joint work with Jugal Garg, Vijay V. Vazirani and Sadra
Yazdanbod

**Abstract:** This talk will give an overview of recent results establishing
connections between the complexity of approximate counting
problems and phase transitions in statistical physics. I will
focus on recent work (with recent ACO graduate Andreas Galanis
and Daniel Stefankovic that appeared in STOC '14) showing
hardness results for approximately counting colorings. The
key tool is a simplified approach for the analysis of spin systems
on random regular graphs.

**Abstract:** A special purpose "quantum computer" manufactured
by the Canadian company D-Wave has led to intense excitement in the
mainstream media (including a Time magazine cover dubbing it "the
infinity machine") and the computer industry, and a lively debate in the
academic community. Scientifically it leads to the interesting question
of whether it is possible to obtain quantum effects on a large scale
with qubits that are not individually well protected from decoherence.

We propose a simple and natural classical model for the D-Wave machine -
replacing their superconducting qubits with classical magnets, coupled
with nearest neighbor interactions whose strength is taken from D-Wave's
specifications. The behavior of this classical model agrees remarkably
well with posted experimental data about the input-output behavior of
the D-Wave machine.

Further investigation of our classical model shows that despite its
simplicity, it exhibits novel algorithmic properties. Its behavior is
fundamentally different from that of its close cousin, classical
heuristic simulated annealing. In particular, the major motivation
behind the D-Wave machine was the hope that it would tunnel through
local minima in the energy landscape, minima that simulated annealing
got stuck in. The reproduction of D-Wave's behavior by our classical
model demonstrates that tunneling on a large scale may be a more subtle
phenomenon than was previously understood.

In this talk I will try to make these results accessible to a general
computer science audience, as well as discuss future prospects for
quantum annealing based quantum computers.

Based on joint work with Seung Woo Shin, Graheme Smith, and John Smolin.

**Abstract:** In this talk, we discuss the Decomposition Conjecture posed by
Barát and Thomassen (2006), which states that for every tree T there exists
a natural number k_T such that, if G is a k_T-edge-connected graph and
|E(T)| divides |E(G)|, then G admits a decomposition into copies of T. This
conjecture was verified for stars, some bistars, paths whose length is a
power of 2, paths of length 3, and, recently, we verified this conjecture
for paths of length 5.
(Joint work with Guilherme O. Mota, Márcio Oshiro and Yoshiko Wakabayashi.)