Columbia University Department of Computer Science



New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, November 30, 2012
Davis Auditorium, Columbia University, New York. External sponsorship by: Google

Please join us on Nov 30 to celebrate the 30th anniversary of the New York Area Theory Day, featuring talks by Sanjeev Khanna, Vijay Vazirani, and two new MacArthur Fellows Maria Chudnovsky and Daniel Spielman.

The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York Metropolitan area for one day of interaction and discussion.  The Theory Day features several (usually 4-5) hour-long presentations by leading theoretical computer scientists about state-of-the-art advances in various areas.  Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.

For directions, please go to:

Lunch will be provided; to get it you must RSVP by sending an email to



9:15 - 9:45	Coffee and bagels

9:45 - 10:00	Prof. Zvi Galil - Opening Remarks

10:00 - 10:55	Prof. Daniel A. Spielman, Yale University
		Sparsification of Graphs: How and Why

10:55 - 11:05	Short break

11:05 - 12:00	Prof. Vijay V. Vazirani, Georgia Tech
		New (Practical) Complementary Pivot Algorithms for Market Equilibria

12:00 - 2:00	Lunch (to be provided)

2:00 - 2:55	Prof. Maria Chudnovsky, Columbia University
		Extending the Gyarfas-Sumner Conjecture

2:55 - 3:15	Coffee break

3:15 - 4:10	Prof. Sanjeev Khanna, University of Pennsylvania 
		Edge-Disjoint Paths in Networks

For directions, please see here

To subscribe to our mailing list, follow instructions at


Xi Chen:
Yevgeniy Dodis:
Baruch Schieber:

Special Thanks for help and support from Zvi Galil, Dean of the
College of Computing, Georgia Tech, who started the New York
Area Theory Day 30 years ago and ran it for the first 15 years as
Columbia University Theory Day.


		Sparsification of Graphs: How and Why

		      Prof. Daniel A. Spielman

			  Yale University

A sparsifier of a graph is an approximation of that graph
by a sparse graph. We will consider spectral approximations. For
example, we will see that expanders are the best sparse approximations
of complete graphs and that spectral approximation is stronger than
cut approximation.

I will explain my favorite use of spectral sparsifiers by showing how
one can use them to quickly solve systems of linear equations in the
Laplacian matrix of a graph.

I will finish by explaining how one can construct nearly-optimal spectral
sparsifiers of arbitrary graphs.


New (Practical) Complementary Pivot Algorithms for Market Equilibria

		      Prof. Vijay V. Vazirani

			    Georgia Tech

Complementary pivot algorithms, in the style of the simplex
algorithm, tend to work well in practice despite having an exponential
worst case behavior -- a case in point being the classic Lemke-Howson
algorithm (1964) for 2-player Nash equilibrium. This algorithm also gives
a direct proof of membership of the problem in the class PPAD and yields
deep structural insights, such as oddness of the number of equilibria.

Our first result accomplishes all of the above for the problem of finding
an equilibrium for an Arrow-Debreu market under separable, piecewise
linear concave utilities. Our second result extends this to markets with

Based on the following paper, and a recent joint work with Jugal Garg
and Ruta Mehta:


	    Extending the Gyarfas-Sumner Conjecture

		     Prof. Maria Chudnovsky

		      Columbia University

The "co-chromatic number" of a graph G is the smallest
number t, such that V(G) can be partitioned into t cliques and stable
sets. Which graphs have bounded co-chromatic number? Let us say
that a family F of graphs is "heroic" if every graph G with no induced
subgraph isomorphic to a member of F has bounded co-chromatic
number (where the bound depends on F). Assuming an old conjecture
of Gyarfas and Sumner, we can completely characterize all finite
heroic families.

The proof relies on the following result. A graph G is "k-split" if V(G)
can be partitioned into two sets A and B, such that A contains no clique
of size k+1, and B contains no stable set of size k+1. Our first result
is that for every k, the minimal non-k-split graphs have bounded size.
As a consequence, we show that for every complete multipartite graph
H1, and every complement of a complete multipartite graph H2, there
exists k, such that every graph G with no induced subgraph isomorphic
to H1 or H2 is k-split. This is joint work with Paul Seymour.

In the final part of the talk, we will discuss recent extensions of this
theorem, obtained in joint work with Alex Scott and Paul Seymour,
where instead of excluding a complete multipartite graph and the
complement of one, two general cographs are excluded.


		Edge-Disjoint Paths in Networks

		      Prof. Sanjeev Khanna

		   University of Pennsylvania

A fundamental problem in combinatorial optimization is the
edge-disjoint paths problem (EDP). We are given a collection of
source-destination pairs in a network, and the goal is to maximize the
number of pairs that can be connected by edge-disjoint paths. Even
special cases of EDP correspond to non-trivial optimization problems,
and the problem becomes NP-hard in highly restricted settings. A
sequence of ideas developed over the past decade has led to great
progress on understanding the approximability of EDP. We will survey
some of this progress and highlight an outstanding remaining question.