The IBM Research/NYU/Columbia Theory Day
External sponsorship by: Google Friday, April 20, 2007
The Theory Day will be held at the Davis auditorium, 412 Schapiro
(CEPSR) building, Columbia University, New York.
Program
9:30  10:00 Coffee and bagels
10:00  10:55 Prof. Piotr Indyk
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
10:55  11:05 Short Break
11:05  12:00 Prof. Maria Chudnovsky
Cycles in Dense Digraphs
12:00  2:00 Lunch break
2:00  2:55 Prof. Michael O. Rabin
Highly Efficient SecrecyPreserving Proofs of Correctness of Computations, and Applications
2:55  3:15 Coffee break
3:15  4:10 Prof. Richard Cole
When Might Markets Be Selfconverging? A Local, Quickly Convergent Tatonnement Algorithm
For directions, please see: http://www.cs.columbia.edu/theory/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
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Prof. Piotr Indyk MIT
The area of geometric functional analysis is concerned with studying
properties of geometric (normed) spaces. A typical question in the
area is: given two geometric spaces X, Y, is there an embedding F of X
into Y so that F distorts the distances between any pair of points by
only a constant factor? One of the classic results of this type is a
constantdistortion embedding of an ndimensional space equipped with
L2 norm, into an O(n)dimensional space equipped with L1 norm (also
known as Dvoretzky's theorem for L1). Embeddings have many interesting
applications, in computer science and beyond. A ubiquitous tool for
constructing such embeddings is the probabilistic method: the mapping
is chosen at random, and one shows that it "works" with high
probability. Unfortunately, this approach does not yield a concrete
(or explicit) construction of an embedding. A folklore open problem
has been to obtain explicit constructions with parameters that
(almost) match the nonconstructive bounds. However, the progress on
this front has been somewhat limited.
For example, the best known
explicit construction of an embedding of an ndimensional L2 space
into an mdimensional L1 space guarantees only m=O(n^{2}). In this talk
I will show an explicit construction of an embedding of an
ndimensional L2 space into L1 space of dimension n^{1+o(1)}. The
construction utilizes two tools: discrete uncertainty principles
(introduced by Donoho and Stark in the area of digital signal
processing) and randomness extractors. If time allows, I will also
show some related constructions, with application to signal sketching
and compressed sensing.
Cycles in Dense Digraphs
Prof. Maria Chudnovsky
Columbia University and Clay Mathematics Institute
The CaccettaHaggkvist conjecture is a problem in graph theory, quite
simple to state, with connections in additive number theory and linear
programming. It was proposed in 1978, and has remained open until
now. The conjecture asserts the following. Let G be a directed graph
with n vertices, and let t be an integer. Suppose that every vertex
has at least n/t outneighbors. Then the graph must have a directed
cycle of length at most t. This has been settled when t is large, and
the case t = 3 seems the most important and challenging unsolved case.
It is easy to see that the CaccettaHaggkvist conjecture holds for
tournaments (these are directed graph in which there is an edge
between every two vertices), and, more generally, one might hope to
take advantage of information about the density of the underlying
graph. Thus, a related question is the following: given a directed
graph with k nonadjacent pairs of vertices in the underlying
undirected graph, and with no directed cycle of length at most three,
how many edges does one need to delete in order to make the directed
graph acyclic? We conjecture that the right answer is k/2. We prove
this in some special cases, and show some natural examples where this
is tight. We also prove a weaker version of the conjecture, with k/2
replaced by k. This is joint work with Paul Seymour and Blair
Sullivan.
Highly Efficient SecrecyPreserving Proofs of Correctness of Computations, and Applications
Prof. Michael O. Rabin
Harvard University and Columbia University
We present a highly efficient method for proving correctness of
computations while preserving secrecy of the input values. This is
done in an EvaluatorProver model which can also be realized by a
secure processor. Applications to secure auctions will be presented.
This is joint work with Rocco Servidio and Chris Thorpe.
When Might Markets Be Selfconverging? A Local, Quickly Convergent Tatonnement Algorithm
Prof. Richard Cole
NYU
How might markets find equilibrium prices? To begin to answer this
question, we consider a subset of divisible markets having unique equilibrium prices; we then describe a price update procedure that
converges toward these prices. We seek procedures with the following
properties:
1. There is a distinct instance of the procedure for each good
2. The procedure is "local": (i) The instances are independent, and (ii) Each instance uses limited local information
3. It is simple
4. It is asynchronous: price updates do not have to be simultaneous
5. It converges quickly
Specifically, we give two tatonnementstyle procedures of this type
which operate in a subset of divisible markets obeying the Weak Gross
Substitutes property, including all markets with CobbDouglas
utilities, and those with CES utilities having rho in the range (0,1),
but bounded away from 1. The first of the procedures requires and uses
an (implicit) upper bound on the elasticity of demand; the second
procedure, loosely speaking, discovers this upper bound. (This is joint work with Lisa Fleischer.)
We will also discuss hardness issues for analogous discrete
markets. (This is joint work with Ashish Rastogi.)
top  contact webmaster@cs.nyu.edu
