๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Topological parameters for time-space tradeoff

โœ Scribed by Rina Dechter; Yousri El Fattah

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
463 KB
Volume
125
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 can select from a spectrum of algorithms, the one that best meets a given time-space specification. To determine the potential of this approach we analyze the structural properties of problems coming from the circuit diagnosis domain. The analysis demonstrates how the tradeoffs associated with various hybrids can be used for each problem instance.

๐Ÿ“œ 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

Timeโ€“Space Tradeoffs for Branching Progr
Timeโ€“Space Tradeoffs for Branching Programs
โœ Paul Beame; T.S. Jayram; Michael Saks ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 265 KB

We obtain the first non-trivial time-space tradeoff lower bound for functions f: {0, 1} n Q {0, 1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length (1+e) n, for some constant e > 0. We also give the firs

Optimal Timeโ€“Space Tradeoff for Shared M
Optimal Timeโ€“Space Tradeoff for Shared Memory Leader Election
โœ Yehuda Afek; Gideon Stupp ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 283 KB

Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational po

Timeโ€“Space Tradeoffs for SAT on Nonunifo
Timeโ€“Space Tradeoffs for SAT on Nonuniform Machines
โœ Iannis Tourlakis ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 176 KB

are generalized and combined with an argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time-space lower bounds for SAT on nonuniform machines. In particular, we show that for any a < `2 and any e > 0, SAT cannot be computed by a ra