Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sabyasachi Basu:

TR21-122 | 24th August 2021
Sabyasachi Basu, Akash Kumar, C. Seshadhri

The complexity of testing all properties of planar graphs, and the role of isomorphism

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

ISSN 1433-8092 | Imprint