Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-098 | 2nd May 2019 12:14

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 2nd May 2019 12:14
Downloads: 547
Keywords: 


Abstract:

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.
That is, for essentially any function $q:(0,1]\to\N$, we prove the existence of properties for which $\epsilon$-testing
has query complexity $\Theta(q(\Theta(\epsilon)))$.
Such results are proved in three standard domains that are often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs.

These results complement hierarchy theorems of Goldreich, Krivelevich, Newman, and Rozenberg (Computational Complexity, 2012), which refer to the dependence of the query complexity on the size of the tested object, and focus on the case that the proximity parameter is set to some small positive constant. We actually combine both flavors and get tight results on the query complexity of testing when allowing the query complexity to depend on both the size of the object and the proximity parameter.



Changes to previous version:

Various low-level presentation improvements


Paper:

TR18-098 | 17th May 2018 11:22

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity





TR18-098
Authors: Oded Goldreich
Publication: 17th May 2018 11:22
Downloads: 835
Keywords: 


Abstract:

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.
That is, for essentially any function $q:(0,1]\to\N$, we prove the existence of properties for which $\epsilon$-testing
has query complexity $\Theta(q(\Theta(\epsilon)))$.
Such results are proved in three standard domains that are often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs.

These results complement hierarchy theorems of Goldreich, Krivelevich, Newman, and Rozenberg (Computational Complexity, 2012), which refer to the dependence of the query complexity on the size of the tested object, and focus on the case that the proximity parameter is set to some small positive constant. We actually combine both flavors and get tight results on the query complexity of testing when allowing the query complexity to depend on both the size of the object and the proximity parameter.



ISSN 1433-8092 | Imprint