本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

Random Walks and Space Complexity
講演者:Francois Le Gall(Kyoto University)
平成30年6月18日(月)15時〜16時30分 理学部7号館地下007講義室
The concept of random walk is an extremely versatile and powerful paradigm in the field of randomized algorithms. In the first part of this talk I will review the concept of random walks and describe several well-known applications concerning the design of space-efficient algorithms (e.g., how to test if an undirected graph is connected in logarithmic space). In the second part of this talk I will present more recent results about space-efficient algorithms for solving linear systems of equations based on random walks.