|
|
Milestone Year
2005
Deterministic simulation of random walks
A simple and not too expensive way of finding a path between two cities in a road map is take a random walk on the map; that is, at each step select a random road going out of the current city and follow it to the neighboring city. Such a method finds a path of length that is polynomial in the number of cities, but it is found by a computation that needs only remember numbers that are of such a size. Can such a path be found by a deterministic algorithm?
The aforementioned question has been opened since the late 1970s, and it was resolved (affirmatively) by a WIS scientist. This resolution is a major achievement in the study of derandomization; that is, the transformation of randomized algorithms into deterministic one.
The deterministic algorithm operates by gradually (and locally) embedding the actual road map in an imaginary one, in which finding paths is very easy, and mapping the path found in the imaginary map to a path in the actual road map. Indeed, it is crucial that both operations can be performed while using a small amount of memory (i.e., an amount that is logarithmic in the number of cities in the map).
In general, WIS scientists made numerous important contributions to the study of derandomization. Notable examples appear in the related milestones on pseudoarndomness and explicit combinatorial constructions.
