Date: 03 Nov 2011 From: jyrki@diku.dk Subject: Talk on computer senility Guest lecture: Designing Algorithms with Limited Work Space Speaker: Tetsuo Asano Time: Tuesday, 8 November 2011 at 14.05–15.00 Place: Lille auditorium (Universitetsparken 1) Abstract: Recent progress in computer systems has provided programmers with virtually unlimited amount of work storage for their programs. This leads to space-inefficient programs that use too much storage and become too slow if sufficiently large memory is not available. Thus, I believe that space-efficient algorithms or memory-constrained algorithms deserve more attention. Constant-work-space algorithms have been extensively studied under a different name, log-space algorithms. Input data are given on a read-only array of $n$ elements, each having O(log n) bits, and work space is limited to O(log n) bits, in other words, a constant number of pointers and counters, each of O(log n) bits. This memory constraint in the log-space algorithms may be too severe for practice applications. For problems related to an image with n pixels, for example, it is quite reasonable to use $O(\sqrt{n})$ work space, which amounts to a constant number of rows and columns. I will start my talk with a simple algorithm for detecting a cycle in a graph using only some constant amount of work space (more exactly, O(log n) bits in total) and then its applications. Then, I will introduce some paradigms for designing such memory-constrained algorithms and their applications to interesting problems including those in computational geometry and computer vision. ------------------------------------------------------------ Dr. Tetsuo Asano was born in Kyoto Prefecture, Japan, in 1949. He got B.E., M.E., and Ph.D degrees from Osaka University, Japan, in 1972, 1974, and 1977, respectively. In 1977 he joined Osaka Electro-Communication University as a lecturer and moved to JAIST (Japan Advanced Institute of Science and technology) in 1997. He is now a professor in School of Information Science. He served as a Presidential Advisor in 1999-2000 and as a senetor in 2001-2003. His research interest includes algorithms and data structures, especially in computational geometry, combinatorial optimization, computer graphics, computer vision using geometric information, and VLSI layout design. He served as editors of several journals including Discrete and Computational Geometry, Computational Geometry: Theory and Applications, International Journal of Computational Geometry and Applications, and Theory of Computing Systems. He is fellows of Association of Computing Machinery (2001), IPS of Japan (2004), and IEICE of Japan (2010). ------------------------------------------------------------ Tetsuo's home page: http://www.jaist.ac.jp/~t-asano PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/