Testing properties of graphs and functions

Simple item page
dc.creatorLovasz, Laszlo
dc.creatorSzegedy, Balazs
dc.date2008-03-08
dc.date2008-03-11
dc.date.accessioned2026-07-07T09:25:51Z
dc.date.available2026-07-07T09:25:51Z
dc.descriptionWe define an analytic version of the graph property testing problem, which can be formulated as studying an unknown 2-variable symmetric function through sampling from its domain and studying the random graph obtained when using the function values as edge probabilities. We give a characterization of properties testable this way, and extend a number of results about ``large graphs'' to this setting. These results can be applied to the original graph-theoretic property testing.
dc.description34 pages
dc.identifierhttps://arxiv.org/abs/0803.1248
dc.identifierhttp://arxiv.org/abs/0803.1248
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/156548
dc.subjectCombinatorics
dc.subjectFunctional Analysis
dc.subject05C99; 68Q99
dc.titleTesting properties of graphs and functions
dc.typetext

Files

Collections

arXiv