Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Oded Schramm:

TR08-010 | 17th January 2008
Itai Benjamini, Oded Schramm, Asaf Shapira

Every Minor-Closed Property of Sparse Graphs is Testable

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

ISSN 1433-8092 | Imprint