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

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 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. 

Organizers:

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 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"