Randomness and Computation

Joint Workshop ``New Horizons in Computing'' and ``Statistical Mechanical Approach to Probabilistic Information Processing''
(MEXT Grant-in-Aid for Scientific Research on Priority Areas)


18 - 21 July, 2005
Sendai International Center, Sendai, Japan

[Japanese Version]



  • Location: Hagi Conference Hall, Sendai International Center, Aobayama, Aoba-ku, Sendai 980-0856, Japan
      (Access Map, Phone +81-22-265-2211CFax +81-22-265-2485)
  • Banquet: 19 July, 2005, Evening, Sendai Excel Hotel Tokyu, Fee: 7000 Japanese Yen per One Person.
  • Technical Program:
      18 July, 2005
        13:15-13:30 [Opening]
        13:30-14:00
          A. Kawachi (Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
          (Title) Approximated two choices in randomized load balancing
          (Extended Abstract) Postscript, PDF,
        14:00-14:30
          K. Amano (Graduate School of Information Sciences, Tohoku University)
          (Title) Random Projection and Its Application to Learning
          (Extended Abstract) PDF
        14:30-15:00
          T. Tsukiji (Graduate School of Science and Engineering, Tokyo Denki University)
          (Title) Limit laws for terminal nodes in random circuits with restricted fan-out
          (Extended Abstract) PDF
        15:00-15:15 Coffee Break
        15:15-15:45
          H. Takahashi (Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
          (Title) On a definition of random sequences with respect to parametric models
          (Extended Abstract) PDF
        15:45-16:15
          K. Tadaki (Chuo University)
          (Title) Algorithmic randomness and quantum measurements in an infinite dimensional quantum system
          (Extended Abstract) Postscript, PDF
        16:15-16:45
          N. Miyoshi (Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
          (Title) Asymptotics of fault probability in LRU caching with dependent and Zipf-type request distributed references
          (Extended Abstract) Postscript, PDF
      19 July, 2005
        10:00-10:30
          O. Watanabe (Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
          (Title) Bisection Problem on Bipartite Graphs
          (Extended Abstract) PDF
        10:30-11:00
          T. Itoh (Global Scientific Information and Computing Center, Tokyo Institute of Technology)
          (Title) Explicit construction of k-wise nearly random permutations by iterated feistel transform
          (Extended Abstract) PDF
        11:00-11:15 Coffee Break
        11:15-11:45
          Y. Shiraishi (Graduate University for Advanced Studies)
          (Title) An upper bound on the convergence time of the Gibbs sampler in Ising models
          (Extended Abstract) Postscript, PDF
        11:45-12:15
          S. Kijima (Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
          (Title) Sampling from multivariate discrete distribution on a simplex -- Markov chain approach --
          (Extended Abstract) Postscript, PDF
        12:15-13:30 Lunch
        13:30-14:00
          A. Suzuki (Graduate School of Information Sciences, Tohoku University)
          (Title) Dense subgraph problem revisited
          (Extended Abstract) Postscript, PDF
        14:00-14:30
          T. Tokuyama (Graduate School of Information Sciences, Tohoku University)
          (Title) Semi-balanced colorings of graphs
          (Extended Abstract) Postscript, PDF
        14:30-14:45 Coffee Break
        14:45-15:45 [Tutorial Talk]
          K. Tanaka (Graduate School of Information Sciences, Tohoku University)
          (Title) Probabilistic image processing and Bayesian network
          (Extended Abstract) Postscript, PDF
          (Lecture Note) Postscript, PDF
          (Presentation Slide) Power Point,
        15:45-16:45 [Tutorial Talk]
          O. Cheong (Division of Computer Science, KAIST, Korea)
          (Title) On finding a guard that sees most and a shop that sells most
          (Lecture Note) PDF
        16:45-17:30 Discussions for Tutorial Talks (O. Cheong, K. Tanaka)
      20 July, 2005
        10:00-10:30
          H. Nishimori (Department of Physics, Tokyo Institute of Technology)
          (Title) Statistical mechanical analysis of quantum toric code
          (Extended Abstract) Postscript, PDF
        10:30-11:00
          Y. Kabashima (Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology)
          (Title) A CDMA multiuser detection algorithm based on survey propagation
          (Extended Abstract) PDF
        11:00-11:15 Coffee Break
        11:15-12:15 [Tutorial Talk]
          K. Hukushima (Graduate School of Arts and Science, University of Tokyo)
          (Title) Monte Carlo method -- sampling from an extended ensemble --
          (Extended Abstract) Postscript, PDF
          (Lecture Note) Postscript, PDF
        12:15-13:30 Lunch
        13:30-14:30 [Tutorial Talk]
          T. Matsui (Graduate School of Information Science and Technology, University of Tokyo)
          (Title) CFTP algorithms for perfect sampling
          (Extended Abstract) Postscript, PDF
          (Lecture Note) Postscript, PDF
        14:30-15:15 Discussions for Tutorial Talks (K. Hukushima, T. Matsui)
        15:15-15:45
          S. Ikeda (Institute of Statistical Mathematics)
          (Title) Information geometrical view of propagation algorithms
          (Extended Abstract) Postscript, PDF
        15:45-16:15
          N. Murata (School of Science and Engineering, Waseda University)
          (Title) Stochastic filtering for on-line boosting
          (Extended Abstract) Postscript, PDF,
        16:15-16:45
          S. Suzuki (Graduate School of Frontier Sciences, University of Tokyo)
          (Title) The quantum annealing and its application in a classical computer
          (Extended Abstract) PDF,
        16:45-17:15
          J. Inoue (Graduate School of Information Science and Technology, Hokkaido University)
          (Title) Quantum spin glasses and probabilistic information processing
          (Extended Abstract) Postscript, PDF,
      21 July, 2005
        10:00-10:30
          J. Ohkubo (Graduate School of Information Sciences, Tohoku University)
          (Title) Generation of complex networks without growth
          (Extended Abstract) Postscript, PDF
        10:30-11:00
          N. Mori (College of Engineering, Osaka Prefecture University)
          (Title) A novel diversity measure of genetic programming
          (Extended Abstract) PDF
        11:00-11:15 Coffee Break
        11:15-11:45
          Y. Motomura (Digital Human Research Center, National Institute of Advance Industrial Science and Technology)
          (Title) Practical information processing using belief propagation and Bayesian networks
          (Extended Abstract) Postscript, PDF,
        11:45-12:15
          T. Murayama (NTT Communication Science Laboratories)
          (Title) Replica symmetry breaking, scaling theory, and sensor networks
          (Extended Abstract) Postscript, PDF
        12:15-13:30 Lunch
        13:30-14:00
          T. Tanaka (Faculty of System Design, Tokyo Metropolitan University)
          (Title) On the eigenvalue spectrum of random matrices
          (Extended Abstract) Postscript, PDF
        14:00-14:30
          K. Nakamura (Faculty of Science and Technology, Keio University)
          (Title) Channel estimation for CDMA multiuser detection
          (Extended Abstract) Postscript, PDF,
        14:30-15:00
          H. Shouno (Department of Engineering, Yamaguchi University)
          (Title) Statistical mechanics of spike analysis model by use of log-linear model
          (Extended Abstract) Postscript, PDF
        15:00-15:15 [Closing]
      * The proceedings including the extended abstracts of all speakers have been distributed free on the days of this workshop.
      * All rights are reserved and no part of all manuscripts in this webpage may be reproduced without written permission from the respective authors.
  • Organizing Committee:
      ``New Horizons in Computing'' (NHC)
        O. Watanabe (Graduate School of Information Science and Engineering, Tokyo Institute of Technology, General Co-Chair)
        T. Tokuyama (Graduate School of Information Sciences, Tohoku University)
      ``Statistical Mechanical Approach to Probabilistic Information Processing'' (SMAPIP)
        K. Tanaka (Graduate School of Information Sciences, Tohoku University, General Co-Chair)
        Y. Kabashima (Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology)
        T. Tanaka (Faculty of System Design, Tokyo Metropolitan University)
        H. Nishimori (Department of Physics, Tokyo Institute of Technology)
  • Links:
      SMAPIP Tutorial ``Probabilistic Information Processing in Bio-Informatics'' (22 July, 2005CSendai International Center, Hagi Conference Hall)
  • Sponsered by:
      ``New Horizons in Computing'' (NHC)
      (MEXT Grant-in-Aid for Scientific Research on Priority Areas)

      ``Statistical Mechanical Approach to Probabilistic Information Processing''
      (MEXT Grant-in-Aid for Scientific Research on Priority Areas)

  • Co-sponsered by:
    1. The Institute of Electronics, Information and Communication Engineers (IEICE)
    2. The Society of Instrument and Control Engineers (SICE)
    3. The Japanese Society for Artificial Intelligence (JSAI)
    4. The Physical Society of Japan
    5. Information Processing Society of Japan (IPSJ)
    6. Japanese Neural Network Society (JNNS)
    7. The Institute of Systems, Control and Information Engineers (ISCIE)
  • Related Workshops of ``New Horizons in Computing'' (MEXT Grant-in-Aid for Scientific Research on Priority Areas):
    1. Workshop on New Horizons in Computing (NHC) -- Recent Trends in Theoretical Computer Science -- (Feb. 28 - Mar. 3, 2005, Kyoto Royal Hotel, Kyoto, Japan)
    2. Computation (COMP) Technical Group, The Institute of Electronics, Information and Communication Engineerings
    3. The 15th Annual International Symposium on Algorithms and Computation (December 20 - 22, 2004, HKUST, Hong Kong
  • Related Workshop of ``Statistical Mechanical Approach to Probabilistic Information Processing''
    (MEXT Grant-in-Aid for Scientific Research on Priority Areas)
    1. Hayashibara Forum 2003 ---Physics and Information--- (11-13 July, 2003, Okayama, Japan).
    2. Satellite Meeting of STATPHYS 22 ``Statistical Physics of Disordered Systems and Its Applications'' (12-15 July, 2004, Shonan Village Center, Hayama, Japan).
    3. Statistical Physics of Disordered Systems and its Applications (SPDSA2005) (5 - 8 September, 2005, Accademia dei Lincei, Roma, Italy).
  • * All rights are reserved and no part of all manuscripts in this webpage may be reproduced without written permission from the respective authors.


    Contact to Kazuyuki Tanaka (E-mail: kazu [at mark] tohoku [dot] ac [dot] jp)