Skip to content

CSM

Seminar

Testing expansion in bounded degree graphs

Czumaj, A (Warwick)
Friday 28 March 2008, 12:15-12:45

Seminar Room 1, Newton Institute

Abstract

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately O(n^{1/2}).

We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an a*-expander with probability at least 2/3, where a* = O(a^2/(d^2 log(n/epsilon))), d is the maximum degree of the graphs, and a graph is called epsilon-far from an a*-expander if one has to modify (add or delete) at least epsilon d n of its edges to obtain an a*-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^2 n^{1/2} log(n/epsilon)/(a^2 epsilon^3)). We will also briefly discuss the recent improvements due to Kale and Seshadhri, Nachmias and Shapira, who reduced the dependency in the expansion of the rejected graphs from O(a^2/(d^2 log(n/epsilon))) to O(a^2/d^2).

Related Links

Presentation

[ppt ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧