Recent Developments in Testing Bounded-Degree Graphs

Although Dana's recent focus has not been on this model, much of the pioneering work was done by her. This includes the introduction of the model, its initial study, and the celebrated tester for Bipartitness, which relies on random walks. After recalling the bounded-degree graph testing model, I will review a few recent developments. I hope to be able to discuss the following three directions. 1. The work of Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021), which is pivoted at constructing locally-characterized expander graphs. The construction makes inherent use of the iterative and local nature of the Zig-Zag construction of Reingold, Vadhan, and Wigderson (41st FOCS, 2000). This yields a locally-characterizable graph property that cannot be tested (in the bounded-degree graph model) within a number of queries that does not depend on the size of the graph. 2. Studies of the (fixed graph and two graph versions of the) Graph Isomorphism problem, including determining the complexity of testing isomorphism to a fixed graph, for almost all regular graphs. 3. Transporting results about functions to results about graphs by using robustly self-ordered graphs, including a separation between tolerant and standard testing in this model (by myself and Wigderson (36th CCC, 2021),