Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Warren Weaver Hall 109
Date: November 18, 2005, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
Network Formation Games and the Price of Anarchy and Stability
Prof. Eva Tardos
Cornell
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 Levi
IBM T.J. Watson Research Center
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.
Notes:
In-person attendance only available to those with active NYU ID cards.