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 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.


top | contact webmaster