On the randomness complexity of property testing

DOI10.1007/s00037-009-0282-4zbMath1204.68097OpenAlexW1989636021MaRDI QIDQ623502

Oded Goldreich, Or Sheffet

Publication date: 7 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0282-4

zbMATH Keywords

samplingproperty testingrandomness extractorsrandomness complexityweak sources of randomness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (9)

Finding cycles and trees in sublinear time ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Succinct interactive oracle proofs: applications and limitations ⋮ Proofs of Proximity for Distribution Testing ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ On the Average-Case Complexity of Property Testing ⋮ On the Power of Relaxed Local Decoding Algorithms

This page was built for publication: On the randomness complexity of property testing