𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Time-Space Tradeoff for Element Distinctness

✍ Scribed by Borodin, A.; Fich, F.; Meyer auf der Heide, F.; Upfal, E.; Wigderson, A.

Book ID
118174140
Publisher
Society for Industrial and Applied Mathematics
Year
1987
Tongue
English
Weight
403 KB
Volume
16
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Time–Space Tradeoffs for Satisfiability
Time–Space Tradeoffs for Satisfiability
✍ Lance Fortnow πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 180 KB

We give the first nontrivial model-independent time space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved in n 1+o(1) time and n 1&= space for any =>0 general random-access nondeterministic Turing machines. In particular, SAT cannot be solved deterministically by a Turing mac

Topological parameters for time-space tr
Topological parameters for time-space tradeoff
✍ Rina Dechter; Yousri El Fattah πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 463 KB

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure, the user ca