### Abstract

Many randomized algorithms run successfully even when the random choices they utilize are not fully independent. For the analysis some limited amount of independence, like k-wise independence for some fixed k, often suffices. In these cases, it is possible to replace the appropriate exponentially large sample spaces required to simulate all random choices of the algorithms by ones of polynomial size. This enables one to derandomize the algorithms, that is, convert them into deterministic ones, by searching the relatively small sample spaces deterministically. If a random variable attains a certain value with positive probability, then we can actually search and find a point in which it attains such a value.

Original language | English (US) |
---|---|

Title of host publication | Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings |

Editors | Rolf Karlsson, Andrzej Lingas |

Publisher | Springer Verlag |

Pages | 1-3 |

Number of pages | 3 |

ISBN (Print) | 3540614222, 9783540614227 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

Event | 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland Duration: Jul 3 1996 → Jul 5 1996 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1097 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 |
---|---|

Country | Iceland |

City | Reykjavik |

Period | 7/3/96 → 7/5/96 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Derandomization via small sample spaces'. Together they form a unique fingerprint.

## Cite this

*Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings*(pp. 1-3). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097). Springer Verlag. https://doi.org/10.1007/3-540-61422-2_115