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/