ACO Student Seminar
Fall 2014


Description

The Georgia Tech ACO Student Seminar is run by students in the ACO program. The objective of the seminar is to give students and postdocs a forum to share their research results or present something of general interest. There will also be occasional survey talks by ACO faculty. The seminar currently meets on Fridays from 1:00-2:00 PM in Skiles 005, and some form of food/drinks will be provided.

Scheduled Talks

September 26: Ioannis Panageas, Coordination games and evolutionary dynamics.

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

October 3: Albert Bush, A multifold sum-product theorem

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.

October 10: Robert Krone, Finite generation of symmetric toric ideals

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.

October 17: Steven Ehrlich, Distributed Submodular Maximization

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.

October 24: Peter Ralli, Inverse Expander Mixing in Hypergraphs

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.

October 31: No seminar this week

November 7: Ruta Mehta, Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness

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

November 14: Eric Vigoda, Phase transitions in approximate counting

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.

November 21 (joint seminar with ARC): Umesh Vazirani, How “Quantum” is the D-Wave Machine?

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.

December 5: Fábio Botler, Decompositions of highly edge-connected graphs

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


Contact

If you are interested in giving a talk at the seminar, you can contact any of the organizers: James Bailey, Emma Cohen, or Ben Cousins.

Other Semesters

Fall 2016; Spring 2016; Fall 2015; Spring 2015; Fall 2014