Chennai Mathematical Institute

Seminars




Property testing
Sourav Chakraborty
University of Chicago.
08-08-07


Abstract

In this talk we will 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. We consider (randomized) algorithms which may obtain samples of the function value or even query the function at arguments of their choice, and seek algorithms of relatively low complexity (i.e., much lower than the size of the function's domain).

Testing graph properties is common in this field. That is given a representation of the graph we want to test whether the graph has some particular property. But the definition of ``far-ness" and the form of queries allowed depends on the representation of the graph.

In this talk we will look at two problem in property testing. First we consider the problem of testing for a particular graph property called ``st -connectedness" is a directed graph. We give an algorithm that make only constant number of queries. The second is a generalization of graph-isomorphism. Here we test whether two strings are same under some transitive group action.

The talk will be self contained and all the definitions and proofs are mostly combinatorial.