Recent Developments in Testing Bounded-Degree Graphs

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.

Recent Developments in Testing Bounded-Degree Graphs