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 TR21-088 | 26th June 2021 20:54

Open Problems in Property Testing of Graphs

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 26th June 2021 20:54
Downloads: 513
Keywords: 


Abstract:

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.
* Characterizing the class of properties that are testable within extremely low complexity.

Turning to the bounded-degree graph model, we discuss several open problems, including:

* Characterizing the class of properties that are testable within size-oblivious complexity.
* Determining the complexity of graph isomorphism.
In each of the foregoing models, we also discuss a favorite open problem that was recently resolved. Lastly, we discuss the vast lack of knowledge with respect to testing graph properties in the general graph model.



Changes to previous version:

Correcting a typo (in Sec 3.2) and adding Footnote 12 relating to it.


Paper:

TR21-088 | 23rd June 2021 16:30

Open Problems in Property Testing of Graphs





TR21-088
Authors: Oded Goldreich
Publication: 23rd June 2021 16:30
Downloads: 962
Keywords: 


Abstract:

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.
* Characterizing the class of properties that are testable within extremely low complexity.

Turning to the bounded-degree graph model, we discuss several open problems, including:

* Characterizing the class of properties that are testable within size-oblivious complexity.
* Determining the complexity of graph isomorphism.
In each of the foregoing models, we also discuss a favorite open problem that was recently resolved. Lastly, we discuss the vast lack of knowledge with respect to testing graph properties in the general graph model.



ISSN 1433-8092 | Imprint