Terry Tao and Gil Kalai have written on the mathematical work of Oded Schramm. Tao suggests a survey paper by Lawler as a source to learn more about the stochastic Loewner equation and its applications. Schramm was a plenary speaker at the 2006 ICM in Madrid, and his talk can be seen going to http://www.icm2006.org/video/ and clicking on “11th Session.” Unfortunately the site is very badly designed and, on my computer, it works neither with Firefox nor with Chrome. (It does work with IE.)

Oded has also worked in computer science, and here I would like to recall a lovely recent paper of his on property testing.

In graph property testing, we are interested in a graph property such as, say, 2-colorability, and we would like to develop very efficient algorithms, at the cost of delivering an approximate answer. The approximation takes the following form: if the graph is 2-colorable, then we want the algorithm to accept with high probability, and if the algorithm accepts with noticeable probablity, then it must be the case that the graph is at least “-close” to 2-colorable. (A similar definition can be given for any other graph property, such as connectivity, planarity, expansion, 3-colorability, and so on.)

The notion of “closeness” can be defined in various ways, which affect the complexity of the problem.

If we deal with dense graphs, we usually define two -vertex graphs to be “-close” if one can be converted into the other by adding or removing at most edges. In this “dense graph model” of property testing, the notion of closeness is loose enough that essentially every natural graph property has very efficient algorithms, whose running time depends only on .

If we deal with sparse graphs, such as graphs whose maximum degree is (think of as a constant, while the number of vertices goes to infinity), then we would say that two graphs are -close if one can be converted into the other by adding or removing up to edges. In this “bounded degree graph model” of property testing, some properties become much harder to test. While 2-colorability, and, in fact, k-colorability for every k, have testers of complexity in the dense graph model, 2-colorability as complexity and and 3-colorability has complexity in the bounded degree model.

Also, some properties are trivial in the dense graph model and non-trivial in the bounded-degree one. Consider planarity: in the dense graph model, a graph is -close to planar if and only if it is -close to the empty graph, and so testing planarity is equivalent to testing emptiness, and thus trivial. In the bounded-degree model, it had been an open question to find a sub-linear time tester for planarity.

In STOC 2008, Benjamini, Schramm and Shapira prove that planarity is testable in the bounded-degree model with complexity that depends only on , and independent of the size of the graph. The same result applies to any graph property defined in terms of excluded minors. Previously, very few properties were known to be testable with complexity dependent only on in this model.

The proof applies more broadly to properties that are “hyper-finite,” meaning that graphs with the property can be broken up into finite-size components after removing a small fraction of edges. The result relies on a previous result by Schramm, studying “limits” of sequences of hyper-finite graphs using the kind of compactness techniques described by Terry Tao in his recent MSRI lectures.

## 4 comments

Comments feed for this article

September 4, 2008 at 11:11 pm

Oded « Combinatorics and more[...] a post to Oded and mentioned connections of his work with computer science. (Luca wrote a later post on Oded’s recent work with Benjamini and Shapira on property testing for planar and [...]

September 15, 2008 at 8:50 am

Oded Schramm « What’s new[...] [Update, Sep 6: A memorial blog to Oded has been set up by his Microsoft Research group here. See also these posts by Gil Kalai, Yuval Peres, and Luca Trevisan.] [...]

October 31, 2008 at 12:53 pm

Oded Schramm « Almost Surely[...] Loewner evolution”). You can read more about him and his mathematics here, here and here. On a more personal note, while I didn’t know Oded very well, I did meet him more then a [...]

July 11, 2010 at 12:48 pm

Felicity CookI have tested 5 different paper products for suitability of recycling into actual sheets of paper, for a school project. I tested egg cartons, paper towels, wrapping paper, magazines, newspapers. I now know the properties of each recycled product eg firm, soft and pliable, easily folded, can be written on, etc. How could I graph those results please?

Thank you if you can help me.

Felicity Cook