Thursday, February 19, Volen 101, 1:30-2:30 pm. (Refreshments at 1:30pm)
We consider the question of determining whether a given object has a predetermined property or is ``far'' from any object having the property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. Thus, testing a property is a relaxation of deciding that property, and it suggests a certain notion of approximation. We consider (randomized) algorithms which may query the function at arguments of their choice, and seek algorithms which query the function at relatively few places.
We focus on studying properties of functions that represent undirected graphs. In contrast to the standard approach in the study of graph algorithms, we are interested in algorithms that observe only a small fraction of the whole graph. We consider algorithms both for the case where graphs are represented by their Adjacency Matrix (which is most appropriate for dense graphs), and the case where graphs are represented by their Incidence Lists (most appropriate for bounded degree graphs). In both cases we present algorithms that observe only a small part of the graph (in some cases only a constant number of edges), and test properties such as being bipartite, having a clique of a certain size, being k-connected and more.
In particular, we focus on the problem of testing bipartiteness. In the adjacency-matrix representation we provide an algorithm whose complexity is independent of the size of the graph. In the incidence-list representation we show that any algorithm must have complexity at least of the order of square root of the size of the graph, and we describe an algorithm whose complexity matches the lower bound (up to poly-logarithmic factors). I will describe both algorithms (which are fairly simple) and give the ideas for their analysis as well as for the proof of the lower bound.
The talk is based on joint work with Oded Goldreich and Shafi Goldwasser, and is self contained.
Host: Liuba Shrira