Open Problems in Property Testing of Graphs
Webpage for a paper by Oded Goldreich
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.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.