The IBM Research/NYU/Columbia Theory Day
External sponsorship by: Google Friday, December 8, 2006
Courant Institute of Mathematical Sciences
New York University
251 Mercer Street, Auditorium 109
New York, NY
Program
9:30  10:00 Coffee and bagels
10:00  10:55 Dr. Julia Chuzhoy (Institute for Advanced Study)
Cut Problems in Graphs: Algorithms and Complexity
10:55  11:05 Short Break
11:05  12:00 Prof. Dan Boneh (Stanford University)
Queries on Encrypted Data
12:00  2:00 Lunch break
2:00  2:55 Prof. Michel Goemans (MIT)
Minimum Bounded Degree Spanning Trees
2:55  3:15 Coffee break
3:15  4:10 Dr. Jonathan Kelner (Institute for Advanced Study and MIT)
A Randomized PolynomialTime Simplex Algorithm for Linear Programming
For directions, please see: http://www.cims.nyu.edu/direct.html
For additional directions, please see: http://cs.nyu.edu/csweb/Location/directions.html
To subscribe to our mailing list, follow instructions at: http://www.cs.nyu.edu/mailman/listinfo/theoryny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
TalRabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com
Rocco Serverdio rocco@cs.columbia.edu
The organizers also thank Google Labs for their generous support.
Abstracts
Cut Problems in Graphs: Algorithms and Complexity
Dr. Julia Chuzhoy
Institute for Advanced Study
Cut problems are fundamental to combinatorial optimization, and they
naturally arise as intermediate problems in algorithm design. The
study of cut problems is inherently connected to the dual notion of
flows. In particular, starting with the celebrated max flowmin cut
theorem, flowcut gaps have been extensively studied and are the basis
for many graph partitioning and routing algorithms.
In this talk we will investigate several wellknown cut problems in
graphs, including multicut and sparsest cut. We will survey some
existing algorithmic techniques and present some recent hardness of
approximation results. In particular, we will show that the flowcut
gap in directed graphs can be as large as polynomial. This is in sharp
contrast with the undirected graphs, where the gap is known to be only
logarithmic.
Queries on Encrypted Data
Prof. Dan Boneh
Stanford University
We will survey a number of recent results on answering queries on
encrypted data. For example, we will present a recent system
supporting comparison queries  given a ciphertext C=E[m] and a
secret key d_i, one can test if m>i, but learn no other information
about m. More general systems can support conjunctive and subset
queries. We will show that encryption schemes supporting queries on
encrypted data lead to efficient traitor tracing systems and are
closely related to other classic problems in cryptography. Our
constructions are mostly based on bilinear maps in groups of composite
order.
This is joint work with Brent Waters. The talk will be self contained.
Minimum Bounded Degree Spanning Trees
Prof. Michel Goemans
MIT
The minimum spanning tree is one the most fundamental combinatorial
optimization problems, and its efficient solution makes it of wide
applicability in a variety of areas, including network design,
routing, communication and clustering. In this talk, I will consider
the variant under the additional restriction that all degrees of the
spanning tree must be at most a given value $k$. The main result I
will describe is that one can efficiently find a spanning tree of
maximum degree at most $k+2$ whose cost is at most the cost of the
optimum spanning tree of maximum degree $k$. This is almost best
possible, as the problem of just deciding whether a graph has a
spanning tree of maximum degree $k$ is NPcomplete.
The approach uses a sequence of simple algebraic, polyhedral and
combinatorial arguments. It illustrates many techniques and ideas in
combinatorial optimization as it involves polyhedral
characterizations, uncrossing, matroid intersection, and graph
orientations (or packing of spanning trees). Little prior knowledge
will be assumed; just a willingness to learn...
The result generalizes to the setting where every vertex has upper and
lower bounds on its degree. It also gives a better understanding for
relaxations of related problems, including the symmetric and
asymmetric traveling salesman problems.
A Randomized PolynomialTime Simplex Algorithm for Linear Programming
Dr. Jonathan Kelner
Institute for Advanced Study and MIT
In this talk, I shall present the first randomized polynomialtime
simplex algorithm for linear programming. Like the other known
polynomialtime algorithms for linear programming, its running time
depends polynomially on the number of bits used to represent its
input. We begin by reducing the input linear program to a special form
in which we merely need to certify boundedness. As boundedness does
not depend upon the righthandside vector, we run the shadowvertex
simplex method with a random righthandside vector. Thus, we do not
need to bound the diameter of the original polytope. Our analysis
rests on a geometric statement of independent interest: given a
polytope Ax <= b in isotropic position, if one makes a polynomially
small perturbation to b then the number of edges of the projection of
the perturbed polytope onto a random 2dimensional subspace is
expected to be polynomial.
This is joint work with Daniel Spielman.
top  contact webmaster@cs.nyu.edu
