Computer Science Colloquium
New York Area Theory Day
IBM/NYU/Columbia,
November 30, 2012
9:30AM
Davis Auditorium, 412 Schapiro (CEPSR) building
Columbia University
New York, NY
Fall 2012 Colloquia Calendar
Host
Columbia University, New York
External sponsorship by: Google
Synopsis
The New York Area Theory Day is a semiannual 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 GyarfasSumner Conjecture
2:55  3:15 Coffee break
3:15  4:10 Prof. Sanjeev Khanna, University of Pennsylvania
EdgeDisjoint Paths in Networks
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theoryny
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 nearlyoptimal 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 LemkeHowson
algorithm (1964) for 2player 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 ArrowDebreu 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 GyarfasSumner Conjecture
Speaker: Prof. Maria Chudnovsky, Columbia University
Abstract: The "cochromatic 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 cochromatic 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 cochromatic
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 "ksplit" 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 nonksplit 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 ksplit. 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: EdgeDisjoint Paths in Networks
Speaker: Prof. Sanjeev Khanna, University of Pennsylvania
Abstract: A fundamental problem in combinatorial optimization is the
edgedisjoint paths problem (EDP). We are given a collection of
sourcedestination pairs in a network, and the goal is to maximize the
number of pairs that can be connected by edgedisjoint paths. Even
special cases of EDP correspond to nontrivial optimization problems,
and the problem becomes NPhard 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.
