Space complexity vs. query complexity

DOI10.1007/s00037-008-0239-zzbMath1149.68032OpenAlexW2026717573MaRDI QIDQ937195

Asaf Shapira, Oded Lachish, Ilan Newman

Publication date: 20 August 2008

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.5992

zbMATH Keywords

complexitylower boundsproperty testingbounded space

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Hierarchy theorems for property testing ⋮ Hierarchy Theorems for Property Testing ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ A combinatorial characterization of smooth LTCs and applications