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
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.)