Seminar on Stochastic Models and Discrete
Geometry
Probabilistic Analysis of Algorithms
The Institute of Statistical Mathematics
4-6-7 Minami-Azabu, Minato-ku, Tokyo
November 16-17, 2004
Update: November 12, 2004
The study of random combinatorial structures
and algorithms has been an active area of
modern research. Deterministic algorithms
may tend to behave differently on different
inputs. For analysis one assumes some reasonable
probability distribution on input instances
to an algorithm as a way of understanding
its ``typical behavior." Experience
in the field shows that it is often hard
to work with exact models, where on the other
hand one can say something meaningful and
precise on the typical ``asymptotic"
behavior of the algorithm operates massive
data sets.
Organizers:
Yoshiaki Itoh,
Hosam M. Mahmoud,
Masaharu Tanemura
List of Speakers:
Tetsuya Hattori (Tohoku University, Sendai)
Hsien-Kuei Hwang (Academia Sinica, Taipei)
Yoshiaki Itoh (ISM)
Hiroshi Maehara (Ryukyu University, Okinawa,
and ISM)
Hosam M. Mahmoud (The George Washington University,
USA, and ISM)
Naoto Miyoshi (Tokyo Institute of Technology)
Tatsuie Tsukiji (Tokyo Denki University)
Osamu Watanabe (Tokyo Institute of Technology)
Information:
Yoshiaki Itoh, 
, Tel +81 3 5421 8763
Program:
Novmber 16 ( Conference room )
1:25-1:30 Hosam M. Mahmoud (The George Washington
University and ISM)
Opening remarks on probabilistic analysis
of algorithms
1:30 -2:10 Hsien-Kuei Hwang (Academia Sinica, Taipei)
Phase changes in random point quadtrees
2:20-3:00 Tetsuya Hattori (Tohoku University, Sendai)
Scaling limit of successive approximations
for $w' = -w^2$ (and its relation to the
problem of rod bisection)
3:10-3:30 Break
3:30-4:10 Hosam M. Mahmoud (The George Washington University
and ISM)
Distribution of distances in random
tries
4:20 -5:00 Hiroshi Maehara (Ryukyu University, Okinawa,
and ISM)
Enumeration problem related to inversions
5:10-5:50 Osamu Watanabe (Tokyo Institute of Technology)
A simple approximated analysis of
Markov
processes
6:10- 8:10 Party
November 17 ( Conference room )
9:30 -10:10 Yoshiaki Itoh (ISM)
Problems of random sequential packing
10:20-10:40 Break
10:40-11:20 Naoto Miyoshi (Tokyo Institute of Technology)
On the asymptotics of fault probability
in
least-recently-used caching with Zipf-type
request distribution
11:30-12:10 Tatsuie Tsukiji (Tokyo Denki University)
Limit laws for terminal nodes in random
circuits
with restricted fan-out: a family of graphs
generalizing binary search trees
12:20-12:25 Closing