Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Laliv Tauber:

TR22-184 | 28th December 2022
Oded Goldreich, Laliv Tauber

Testing in the bounded-degree graph model with degree bound two

Considering the bounded-degree graph model, we show that if the degree bound is two,
then every graph property can be tested within query complexity that only depends on the proximity parameter.
Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.
The key observation is that a ... more >>>

ISSN 1433-8092 | Imprint