Fall 2013

Fast Testing of Graph Properties

Tuesday, September 17th, 2013 4:00 pm4:45 pm

Add to Calendar

We review recent results for sublinear-time testing of fundamental graph properties in sparse graphs.

We consider the problem in which an input graph G is represented as an adjacency matrix and we're asking a question whether G has a given property P or is "far" from any graph satisfying P. The central question in this area is which properties can be tested very quickly, in particular, in constant-time, independently of the size of the input graph.

We will present recent advances in this area, focusing on planar graphs and graphs with poor expansion properties.

This is talk is based on joint papers with Christian Sohler and others.