The IBM Research/NYU/Columbia Theory Day
Friday, November 18, 2005
Courant Institute of Mathematical Sciences
New York University
251 Mercer Street
Room 109 Warren Weaver Hall
New York, NY
Program
9:30  10:00 Coffee and bagels
10:00  10:55 Prof. Eva Tardos (Cornell)
Network Formation Games and the Price of Anarchy and Stability
10:55  11:05 Short Break
11:05  12:00 Dr. Retsef Levi (IBM T.J. Watson Research Center)
Provably NearOptimal Policies for Hard Stochastic Inventory Control Policies
12:00  2:00 Lunch break
2:00  2:55 Prof. Mario Szegedy (Rutgers University)
Notorious issues concerning Quantum walks
2:55  3:15 Coffee break
3:15  4:10 Prof. Salil Vadhan (Harvard University)
The Complexity of Zero Knowledge
For directions, please see: http://www.cims.nyu.edu/direct.html
For additional directions, please see: http://cs.nyu.edu/csweb/Location/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 Shieber talr@watson.ibm.com
Cliff Stein cliff@ieor.columbia.edu
Abstracts
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 NearOptimal 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 latenesspenalty 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 nearoptimal. 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 longstanding problem of
finding computationally efficient and provably good inventory control
policies for these models in the presence of correlated and nonstationary
(timedependent) demands. Here the correlation is intertemporal, 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
DualBalancing policies that are the first computationally efficient
policies with worstcase guarantees. Specifically, these policies admit a
worstcase 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
samplingbased 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 samplingbased 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 speedups 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 speedups 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 zeroknowledge
proofs has been one of the most fertile grounds for interaction between
cryptography and complexity theory. On one hand, zeroknowledge proofs and
their cryptographic applications naturally raise interesting complexity
issues, such as tradeoffs between various efficiency measures and the
minimal assumptions needed to construct zeroknowledge 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 complexitytheoretic study of
zeroknowledge proofs, including our recent work providing an unconditional
characterization of "computational" zero knowledge.
top  contact webmaster@cs.nyu.edu
