Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Schapiro (CEPSR) Building, Columbia University 412
Date: November 30, 2012, 9:30 a.m.
Host: Columbia University, New York
Synopsis:
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 meeting is free and open to everyone;
in particular, students are encouraged to attend.
For directions, please go to: http://www.cs.columbia.edu/theory/directions.html
Lunch will be provided; to get it you must RSVP by sending an email to theorydayny@gmail.com.
Program
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
To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny
Organizers:
Xi Chen: xichen@cs.columbia.edu Yevgeniy Dodis: dodis@cs.nyu.edu Baruch Schieber: sbar@us.ibm.com
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.
==================
Title: Sparsification of Graphs: How and Why Speaker: Prof. Daniel A. Spielman, Yale University
Abstract: 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.
==================
Title: New (Practical) Complementary Pivot Algorithms for Market Equilibria Speaker: Prof. Vijay V. Vazirani, Georgia Tech
Abstract: 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 production.
Based on the following paper, and a recent joint work with Jugal Garg and Ruta Mehta: http://www.cc.gatech.edu/~vazirani/SPLC.pdf
==================
Title: Extending the Gyarfas-Sumner Conjecture Speaker: Prof. Maria Chudnovsky, Columbia University
Abstract: 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.
==================
Title: Edge-Disjoint Paths in Networks Speaker: Prof. Sanjeev Khanna, University of Pennsylvania
Abstract: 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.
Notes:
In-person attendance only available to those with active NYU ID cards.