Testing sparse graph properties
318 views · Published 13 April 2016 · 1:24:40 · Indexed 18 November 2026
Channel: ФКН НИУ ВШЭ · 2016 · Education
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
-
1:18:31
[Коллоквиум]: On scale invariance, multifractal formalism, and their applications
-
1:09:43
[Коллоквиум]: Resourse Allocation in the Cloud - Assaf Schuster, Techion
-
1:08:04
[ИТ-лекторий] Занимательная прикладная аналитика в Яндексе
-
1:17:41
[Коллоквиум]: Probabilistic graphical models: Factor graphs and more
-
1:05:46
[Коллоквиум]: Process Mining: Data Science in Action - Wil van der Aalst
-
2:18
[Презентация факультета в ДК ЗИЛ]: Григорий Бакунов, директор по распрост. инф. технологий Яндекс
-
2:55
[Презентация факультета в ДК ЗИЛ]: Григорий Канторович, проректор по работе с абитуриентами ВШЭ
-
11:34
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук