#### 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.