Title: Testing large directed graphs

Speaker: Noga Alon, Tel Aviv University and Institute for Advanced Study

Date: January 28, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A digraph G on n vertices is epsilon-far from satisfying a property P, if one has to add to or delete from G at least epsilon n^2 directed edges to obtain a digraph satisfying P. An epsilon-tester for P is a randomized algorithm that, given n, an access to a digraph G on n vertices, and the ability to ask queries of the form "is (i,j) a directed edge ?"can distinguish, with high probability, between the case that G satisfies P and the case that G is epsilon-far from satisfying P. The tester is a one-sided tester if it does not err on graphs satisfing P. For a fixed digraph H, let P(H) denote the property that G is H-free. We show that for every fixed H, there is an epsilon-tester for P(H) whose query complexity is independent of n. We further characterize all digraphs H for which this complexity (for one-sided error, or two-sided error testers) is polynomial in (1/epsilon), and show that for all of them there is a two-sided tester sampling only O(1/epsilon) vertices, though one sided testers must sample at least (1/\epsilon)^{\Omega(d)} vertices, where d is the average degree of H. Joint work with Asaf Shapira.