From Erdős to algorithms (Q1344623)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: From Erdős to algorithms |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | From Erdős to algorithms |
scientific article |
Statements
From Erdős to algorithms (English)
0 references
13 February 1995
0 references
The probabilistic method of Paul Erdős proves the existence of an object by showing that an appropriately defined random object has a positive probability of having the desired property. This can lead to a probabilistic algorithm for creating the object. A number of instances are given in this semi-expository paper in which a weight function may be used to derandomize the algorithm, yielding a deterministic efficient algorithm to find the object.
0 references
probabilistic algorithm
0 references
0 references
