Seminars & Colloquia

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.