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 the normal view instead:
scientific article; zbMATH DE number 722495
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | From Erdős to algorithms |
scientific article; zbMATH DE number 722495 |
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
