Seminars and Colloquia by Series

Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 2)

Series
Joint ACO and ARC Colloquium
Time
Wednesday, November 6, 2019 - 12:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Nima Anari – Stanford University

(This is Part 2, continuation of Tuesday's lecture.)

A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the efficiency of this method is how quickly the random walk mixes (converges to the stationary distribution). The goal of these talks is to introduce a new approach for analyzing the mixing time of random walks on high-dimensional discrete objects. This approach works by directly relating the mixing time to analytic properties of a certain multivariate generating polynomial. As our main application we will analyze basis-exchange random walks on the set of bases of a matroid. We will show that the corresponding multivariate polynomial is log-concave over the positive orthant, and use this property to show three progressively improving mixing time bounds: For a matroid of rank r on a ground set of n elements:

- We will first show a mixing time of O(r^2 log n) by analyzing the spectral gap of the random walk (based on related works on high-dimensional expanders).

- Then we will show a mixing time of O(r log r + r log log n) based on the modified log-sobolev inequality (MLSI), due to Cryan, Guo, Mousa.

- We will then completely remove the dependence on n, and show the tight mixing time of O(r log r), by appealing to variants of well-studied notions in discrete convexity.

Time-permitting, I will discuss further recent developments, including relaxed notions of log-concavity of a polynomial, and applications to further sampling/counting problems.

Based on joint works with Kuikui Liu, Shayan OveisGharan, and Cynthia Vinzant.

Rapidly Mixing Random Walks via Log-Concave Polynomials (Part 1)

Series
Joint ACO and ARC Colloquium
Time
Tuesday, November 5, 2019 - 15:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
Nima Anari – Stanford University

A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the efficiency of this method is how quickly the random walk mixes (converges to the stationary distribution). The goal of these talks is to introduce a new approach for analyzing the mixing time of random walks on high-dimensional discrete objects. This approach works by directly relating the mixing time to analytic properties of a certain multivariate generating polynomial. As our main application we will analyze basis-exchange random walks on the set of bases of a matroid. We will show that the corresponding multivariate polynomial is log-concave over the positive orthant, and use this property to show three progressively improving mixing time bounds: For a matroid of rank r on a ground set of n elements:

- We will first show a mixing time of O(r^2 log n) by analyzing the spectral gap of the random walk (based on related works on high-dimensional expanders).

- Then we will show a mixing time of O(r log r + r log log n) based on the modified log-sobolev inequality (MLSI), due to Cryan, Guo, Mousa.

- We will then completely remove the dependence on n, and show the tight mixing time of O(r log r), by appealing to variants of well-studied notions in discrete convexity.

Time-permitting, I will discuss further recent developments, including relaxed notions of log-concavity of a polynomial, and applications to further sampling/counting problems.

Based on joint works with Kuikui Liu, Shayan OveisGharan, and Cynthia Vinzant.

Probabilistic analysis of some combinatorial optimization problems

Series
Joint ACO and ARC Colloquium
Time
Wednesday, September 23, 2015 - 11:05 for 1 hour (actually 50 minutes)
Location
Klaus 1116 E
Speaker
Alan Frieze – Carnegie Mellon University
We consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path. Joint work with Colin Cooper and Wesley Pegden.

Algorithm Frameworks Based on Structure Preserving Sampling

Series
Joint ACO and ARC Colloquium
Time
Monday, August 31, 2015 - 13:05 for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Richard Peng – School of Computer Science, Georgia Tech
Sampling is a widely used algorithmic tool: running routines on a small representative subset of the data often leads to speedups while preserving accuracy. Recent works on algorithmic frameworks that relied on sampling graphs and matrices highlighted several connections between graph theory, statistics, optimization, and functional analysis. This talk will describe some key ideas that emerged from these connections: (1) Sampling as a generalized divide-and-conquer paradigm. (2) Implicit sampling without constructing the larger data set, and its algorithmic applications. (3)What does sampling need to preserve? What can sampling preserve? These ideas have applications in solvers for structured linear systems, network flow algorithms, input-sparsity time numerical routines, coresets, and dictionary learning.

Interlacing Families and Bipartite Ramanujan Graphs

Series
Joint ACO and ARC Colloquium
Time
Monday, December 9, 2013 - 15:05 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Adam Marcus – Crisply.com and Yale University
We will outline the proof that shows the existence of bipartite Ramanujan Graphs of any degree as well as some of mixed degrees. Our approach uses the idea of Bilu and Linial to show that there exists a 2-lift of a given Ramanujan graph which maintains the Ramanujan property. This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials." This talk is intended to be accessible by a general computer science audience, and represents joint work with Dan Spielman and Nikhil Srivastava.- See more at: http://www.arc.gatech.edu/events/arc-colloquium-adam-marcus-crisplycom-and-yale-university#sthash.qdZRaV1k.dpuf

Deletion without Rebalancing in Balanced Search Trees

Series
Joint ACO and ARC Colloquium
Time
Friday, April 1, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
TSRB Banquet Hall, 85 5th St.
Speaker
Robert Tarjan – Princeton University
Deletion in a balanced search tree is a problematic operation: rebalancing on deletion has more cases than rebalancing on insertion, and it is easy to get wrong. We describe a way to maintain search trees so that rebalancing occurs only on insertion, not on deletion, but the tree depth remains logarithmic in the number of insertions, independent of the number of deletions. Our results provide theoretical justification for common practice in B-tree implementations, as well as providing a new kind of balanced binary tree that is more efficient in several ways than those previously known. This work was done jointly with Sid Sen. This is a day-long event of exciting talks by meta-learning meta-theorist Nina Balcan, security superman Wenke Lee and prolific mathematician Prasad Tetali, posters by the 10 ARC fellowship winners for the current academic year. All details are posted at http://www.arc.gatech.edu/arc4.php. The event begins at 9:00AM.

From the "slicing problem" to "KLS Conjecture": The concentration of measure phenomenon in log-concave measures

Series
Joint ACO and ARC Colloquium
Time
Monday, March 7, 2011 - 13:30 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Grigoris Paouris – Texas A &M University

Please Note: Tea and light refreshments 2:30 p.m.  in Room 2222

We will discuss several open questions on the concentration of measure on log-concave measures and we will present the main ideas of some recent positive results.

Counting contingency tables: algorithms and asymptotics

Series
Joint ACO and ARC Colloquium
Time
Monday, November 2, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Klaus 1116W
Speaker
Alexander Barvinok – University of Michigan

Please Note: Tea and light refreshments 1:30 in Room 2222. Organizer: Santosh Vempala

I will discuss recent progress on the construction of randomized algorithms for counting non-negative integer matrices with prescribed row and column sums and on finding asymptotic formulas for the number of such matrices (also known as contingency tables). I will also discuss what a random (with respect to the uniform measure) non-negative integer matrix with prescribed row and column sums looks like.

A survey of sparse approximation

Series
Joint ACO and ARC Colloquium
Time
Thursday, October 29, 2009 - 11:05 for 1 hour (actually 50 minutes)
Location
MiRC 102
Speaker
Anna Gilbert – Mathematics, University of Michigan
The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems and their solutions, including connections to streaming algorithms and compressive sensing.