Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Recent Developments in Testing Bounded-Degree Graphs

Simons Institute via YouTube

Overview

Explore recent developments in testing bounded-degree graphs in this 46-minute lecture by Oded Goldreich at the Simons Institute's Workshop on Local Algorithms (WoLA). Begin with a review of the bounded-degree graph testing model, acknowledging Dana's pioneering work in introducing and initially studying the model, including her celebrated tester for Bipartitness using random walks. Delve into three key directions: First, examine the work of Adler, Kohler, and Peng on constructing locally-characterized expander graphs, which utilizes the Zig-Zag construction to create a locally-characterizable graph property that cannot be efficiently tested. Second, investigate studies on the Graph Isomorphism problem, including determining the complexity of testing isomorphism to a fixed graph for almost all regular graphs. Finally, learn about transporting results from functions to graphs using robustly self-ordered graphs, including a separation between tolerant and standard testing in this model by Goldreich and Wigderson.

Syllabus

Recent Developments in Testing Bounded-Degree Graphs

Taught by

Simons Institute

Reviews

Start your review of Recent Developments in Testing Bounded-Degree Graphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.