Seminars & Colloquia

Wednesday, September 23, 2015

Probabilistic analysis of some combinatorial optimization problems

Wed, 09/23/2015 - 11:05am, Klaus 1116 E

Alan Frieze, Carnegie Mellon University        Organizer: Robin Thomas

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.

Monday, August 31, 2015

Algorithm Frameworks Based on Structure Preserving Sampling

Mon, 08/31/2015 - 1:05pm, Klaus 1116

Richard Peng, School of Computer Science, Georgia Tech         Organizer: Robin Thomas

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.

Monday, December 9, 2013

Interlacing Families and Bipartite Ramanujan Graphs

Mon, 12/09/2013 - 3:05pm, Klaus 1116W

Adam Marcus, and Yale University        Organizer: Prasad Tetali

  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:  

Friday, April 1, 2011

Deletion without Rebalancing in Balanced Search Trees

Fri, 04/01/2011 - 11:00am, TSRB Banquet Hall, 85 5th St.

Robert Tarjan, Princeton University        Organizer:

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 The event begins at 9:00AM.

Monday, March 7, 2011

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

Mon, 03/07/2011 - 1:30pm, Klaus 1116W

Grigoris Paouris, Texas A &M University        Organizer:

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.

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

Monday, November 2, 2009

Counting contingency tables: algorithms and asymptotics

Mon, 11/02/2009 - 2:00pm, Klaus 1116W

Alexander Barvinok, University of Michigan        Organizer:

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.

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

Thursday, October 29, 2009

A survey of sparse approximation

Thu, 10/29/2009 - 11:05am, MiRC 102

Anna Gilbert, Mathematics, University of Michigan        Organizer: Prasad Tetali

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.