The IBM Research/NYU/Columbia Theory Day

External sponsorship by: Google

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 Secrecy-Preserving Proofs of Correctness of Computations, and Applications

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Richard Cole
When Might Markets Be Self-converging? A Local, Quickly Convergent Tatonnement Algorithm

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 constant-distortion embedding of an n-dimensional 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 non-constructive bounds. However, the progress on this front has been somewhat limited.

For example, the best known explicit construction of an embedding of an n-dimensional L2 space into an m-dimensional L1 space guarantees only m=O(n²). In this talk I will show an explicit construction of an embedding of an n-dimensional 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 Caccetta-Haggkvist 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 out-neighbors. 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 Caccetta-Haggkvist 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 non-adjacent 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 Secrecy-Preserving 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 Evaluator-Prover 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 Self-converging? 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 tatonnement-style procedures of this type which operate in a subset of divisible markets obeying the Weak Gross Substitutes property, including all markets with Cobb-Douglas 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.)