Look Who it Was Random video

Testing sparse graph properties

318 views · Published 13 April 2016 · 1:24:40 · Indexed 24 September 2026

Channel: ФКН ВШЭ · 2016 · Education

Watch on YouTube

For a graph on n vertices, and an integer D, let the D-local view of G=(V,E) be the collection (multiset) of the unlabelled n balls of distance D around the vertices.
The main question that motivates this study is: what can be said about G knowing only its D-local view for some constant D.
For constant bounded degree planar (or more generally hyperfinite) graphs, Newman-Sohler [2011] following a long sequence of work, show that for any ε more than 0, there is a D such that the D-local view of the graph determines the graph up to the deletion/insertion of at most εn edges. This in turn, implies that every property of planar (hyperfinite) graphs can be tested (in the sense of property testing, by constantly many queries.
What happens in non-bounded degree planar graphs? The answer is currently still open. However, we show, following Yoshida's results on Forests, that the above phenomenon still holds for outerplanar graphs. The implication to testing is deteriorated, though. Testing now requires O(poly(log n)) queries.
I will describe the ideas behind the two results, the latter which is joint work with Jasine Babu and Areej Khoury.

Speaker: Ilan Newman, University of Haifa.

Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab/tcs2016/
Faculty of Computer Science: https://cs.hse.ru/en/
Follow us: https://www.facebook.com/hsefcs, https://twitter.com/CS_HSE

More from this channel