Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Warren Weaver Hall 109
Date: December 8, 2006, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
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 flow-min cut theorem, flow-cut gaps have been extensively studied and are the basis for many graph partitioning and routing algorithms.
In this talk we will investigate several well-known 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 flow-cut 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 NP-complete.
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 Polynomial-Time Simplex Algorithm for Linear Programming
Dr. Jonathan Kelner
Institute for Advanced Study and MIT
In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time 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 right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side 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 2-dimensional subspace is expected to be polynomial.
This is joint work with Daniel Spielman.
Notes:
In-person attendance only available to those with active NYU ID cards.