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 semiannual
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 45) hourlong
presentations by leading theoretical computer scientists about
stateoftheart 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.
Program:
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 NearOptimal 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.
Organizers:
Yevgeniy Dodis (NYU)
Tal Rabin (IBM Research)
Baruch Schieber (IBM
Research)
Cliff Stein (Columbia)
Abstracts:
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 NearOptimal 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 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.
"Every day is Theory Day"
