|
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:
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:
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
For directions, please see here
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.
==================================================================
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
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
==================================================================
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.
==================================================================
|
