𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On The Randomness Complexity of Property Testing

✍ Scribed by Oded Goldreich; Or Sheffet

Publisher
Springer
Year
2010
Tongue
English
Weight
631 KB
Volume
19
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On testing the β€˜pseudo-randomness’ of a
On testing the β€˜pseudo-randomness’ of a hypergraph
✍ Julie Haviland; Andrew Thomason πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 405 KB

Haviland, J. and A. Thomason, On testing the 'pseudo-randomness' of a hypergraph, Discrete Mathematics 103 (1992) 321-327. By Haviland and Thomason (1989) a definition for a pseudo-random hypergraph was proposed, and the resemblance between these pseudo-random hypergraphs and random hypergraphs was

On the complexity of diagram testing
On the complexity of diagram testing
✍ Graham Brightwell πŸ“‚ Article πŸ“… 1993 πŸ› Springer Netherlands 🌐 English βš– 483 KB
On Randomized Semi-algebraic Test Comple
On Randomized Semi-algebraic Test Complexity
✍ Peter BΓΌrgisser; Marek Karpinski; Thomas Lickteig πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 704 KB
Complexity, randomness, discretization:
Complexity, randomness, discretization: Some remarks on a program of J. Ford
✍ Tyll KrΓΌger; Serge Troubetzkoy πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 604 KB

We discuss certain aspects of the complexity of periodic orbits of chaotic dynamical systems in a symbolic setting. Our theory is based on a generalization of the notion of random sequences in the sense of Kolmogorov and Martin-L6f. Applying our results to the systems studied by Ford et al. leads to