Columbia University Department of Computer Science

The IBM Research | NYU | Columbia THEORY DAY
Friday, November 18, 2005

New York University, Courant Institute 
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 10012

The IBM Research | NYU | Columbia 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 Theory Day features several (usually 4-5) hour-long
presentations by leading theoretical computer scientists about state-of-the-art advances
in various areas.  Some presentations give a survey of the latest advances in some area,
while others may concentrate on a particular result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.


 9:30  - 10:00   Coffee and bagels

10:00 - 10:55 Prof. Eva Tardos
Network Formation Games and the Price of Anarchy and Stability

10:55 - 11:05 Short break

11:05 - 12:00 Dr. Retsef Levy
Provably Near-Optimal Policies for Hard Stochastic Inventory Control Policies

12:00 - 2:00 Lunch break

2:00 - 2:55 Prof. Mario Szegedy
Notorious Issues concerning Quantum Walks

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Salil Vadhan
The Complexity of Zero Knowledge

The Theory Day will be held at Room 109 Warren Weaver Hall,
Courant Institute of Mathematical Sciences, New York University,
251 Mercer Street, New York, NY 10012
Click here or here for directions.

To subscribe to our mailing list, follow instructions here.


Yevgeniy Dodis (NYU)

Tal Rabin (IBM Research)

Baruch Schieber (IBM Research)

Cliff Stein (Columbia)


Network Formation Games and the Price of Anarchy and Stability
Prof. Eva Tardos
(Cornell University)
Traditional network design assumes that the network designer has the information and power to decide on the whole network. However, many networks operate and evolve through interactions of large numbers of participants. Such networks play a fundamental role in many domains, ranging from communication networks to social networks. In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function, caring only about his cost and his part of the network. Our goal is to quantify the degradation of quality of solution caused by the selfish behavior of users, compared to a centrally designed optimum.
Provably Near-Optimal Policies for Hard Stochastic Inventory Control Policies
Dr. Retsef Levy
(IBM Research)
Stochastic inventory theory provides streamlined models in which the goal is to coordinate a sequence of orders of a single commodity, aiming to supply stochastic demands over a discrete finite horizon with minimum expected overall ordering, holding and lateness-penalty costs. Computing the optimal policies for these fundamental models seems to be tractable only under rather strong and usually unrealistic assumptions. In particular, the common unrealistic assumptions are that the stochastic demands in different periods are independent of each other or follow a Markovian process with a small state space and that their distributions are given explicitly as part of the input. In this talk, we relax each one of these assumptions and address the more general and harder variants of these inventory models. Instead of finding optimal policies, which seems to be intractable, we construct policies that can be computed efficiently and are provably near-optimal. That is, the expected cost of the policies is guaranteed to be at most C times the optimal expected cost (for some constant C), regardless of the specific instance of the problem. In the first part of the talk, we address the long-standing problem of finding computationally efficient and provably good inventory control policies for these models in the presence of correlated and non-stationary (time-dependent) demands. Here the correlation is inter-temporal, i.e., what we observe in the current period changes our forecast for the demand in future periods. This problem arises in many domains and has many practical applications in supply chain management. We use novel marginal cost accounting approach and cost balancing techniques to construct Dual-Balancing policies that are the first computationally efficient policies with worst-case guarantees. Specifically, these policies admit a worst-case guarantee of 2 for a broad class of fundamental stochastic inventory models. In the second part of the talk, we consider these models with independent demands but under the assumption that the explicit demand distributions are not known and that the only information available is a set of independent samples drawn from the true distributions (this corresponds to historical data or simulation setting). We shall describe how to compute sampling-based policies, that is, policies that are computed based only on observed samples of the demands without any access to, or assumptions on, the true demand distributions. Moreover, we establish bounds on the number of samples required to guarantee that with high probability, the expected cost of the sampling-based policies is arbitrarily close (i.e., with arbitrarily small relative error) to the expected cost of the optimal policies which have full access to the demand distributions. The bounds that we develop are general, easy to compute and surprisingly do not depend at all on the specific demand distributions. This talk is based on joint work with Ganesh Janakiraman, Mahesh Nagarajan, Martin Pa'l, Robin Roundy, David Shmoys and Van Anh Truong.
Notorious issues concerning Quantum walks
Prof. Mario Szegedy
(Rutgers University)
Only a few methods are known to produce quantum speed-ups over classical algorithms - one such method is the quantum walk. What are quantum walks and what are the most pressing open questions about them? Can we get exponential speed-ups by using them? Is there a fundamental difference between discrete and continuous time walks? We survey some results of Grover, Kempe, Childs, Cleve, Deotto, Farhi, Gutmann and Spielman, and we present a general result stating that the hitting time of every symmetric classical Markov Chain can be sped up quadratically in the quantum world. Grover search is a special case of this, where the walk is done on the complete graph.
The Complexity of Zero Knowledge
Prof. Salil Vadhan
(Harvard University)
Together with the theory of pseudorandomness, the study of zero-knowledge proofs has been one of the most fertile grounds for interaction between cryptography and complexity theory. On one hand, zero-knowledge proofs and their cryptographic applications naturally raise interesting complexity issues, such as tradeoffs between various efficiency measures and the minimal assumptions needed to construct zero-knowledge proofs. On the other hand, the study of proofs is intimately related to the central questions of complexity theory, and zero knowledge enriches this study by incorporating such intriguing concepts as interaction, randomness, knowledge, and secrecy. In this talk, we survey some of the complexity-theoretic study of zero-knowledge proofs, including our recent work providing an unconditional characterization of "computational" zero knowledge.

"Every day is Theory Day"