Recent Developments in Testing Bounded-Degree Graphs
summary
Bounded-degree graphs are tested via the incident-function oracle with constant degree d; the talk gives three concrete developments: a two-graph isomorphism tester has a tilde n^{2/3} lower bound on queries; testing isomorphism to a fixed d-regular H is shown, for almost all H, to need about n·√n queries (matching upper and lower bounds); and a reduction from PCP-based string hardness plus robustly self-ordered graphs and a locally-characterized expander (via zig‑zag/replacement ideas of Reingold–Vadhan–Wigderson and Adler–Kohler–Peng) yields a property with easy standard tests but near-linear tolerant-test complexity.
AI-written summary · about