Hierarchy theorems for testing properties in size-oblivious query complexity

DOI10.1007/s00037-019-00187-2zbMath1494.68091MaRDI QIDQ2281254

Oded Goldreich

Publication date: 19 December 2019

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

Full work available at URL: https://doi.org/10.1007/s00037-019-00187-2

zbMATH Keywords

graph properties; property testing; hierarchy theorems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W20: Randomized algorithms