Home * People * Walter Kosters

Walter A. Kosters,
a Dutch computer scientist and mathematician, and associate professor of CS at LIACS, the Leiden Institute of Advanced Computer Science at Leiden University. His research interests include neural networks, genetic algorithms, analysis of algorithms, concrete mathematics, NP-completeness, bioinformatics, data mining and artificial intelligence. Along with Hendrik Jan Hoogeboom et al., Walter Kosters works on the computational complexity of Tetris [1], and maintains the How to Construct Tetris Configurations site [2].
Walter Kosters [3]


Along with Joost Batenburg, Walter Kosters researches on Nonograms [4], picture logic puzzles where a pixel grid has to be filled with black and white pixels, based on a description that indicates the lengths of the consecutive black segments for each row and column. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column. While the Nonograms that can be found in puzzle books can typically be solved by applying a series of highly local reasoning steps regarding single rows and columns, the general Nonogram problem is NP-hard.

Selected Publications


External Links


  1. ^ Tetris is Hard: An Introduction to P vs NP (pdf) slides based on Erik D. Demaine, Susan Hohenberger, David Liben-Nowell (2003). Tetris is Hard, Even to Approximate. COCOON 2003
  2. ^ How to Construct Tetris Configurations
  3. ^ Walter Kosters
  4. ^ Nonogram — Turn your picture into a puzzle
  5. ^ DBLP: Walter A. Kosters

What links here?

Up one level