Title: Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
Speaker: Xi Chen, Columbia University
Date: Wednesday, October 2, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We analyze the 2-dimensional Weisfeiler-Leman (2-dim WL) refinement, an extension of the naive refinement heuristic for isomorphism testing, over Steiner 2-systems. A Steiner 2 -system consists of points and lines, where each line passes the same number of points and each pair of points uniquely determines a line. Each Steiner 2-system induces a Steiner graph, in which vertices represent lines and edges represent intersections of lines. Steiner graphs are an important subfamily of strongly regular graphs whose isomorphism testing has challenged researchers for years. Inspired by the previous analyses of the individualization and refinement method by Babai and by Spielman, we show that the individualization of O(log n) points and lines suffices for the 2-dim WL refinement to distinguish all pairs of points of a Steiner 2-system. As a result, the isomorphism of Steiner 2-systems with n lines can be tested in time n^{O(log n)}, improving the previous best upper bound of exp(\tilde{O}(n^{1/4})) by Spielman. Before our result, quasipolynomial-time isomorphism testing was only known for the case when the line size is polylogarithmic, as shown by Babai and Luks.
A result essentially identical to ours was obtained simultaneously by Babai and Wilmes. They performed a direct analysis of the individualization and refinement method based on the naive refinement, building on a different philosophy and combinatorial structure theory.
Joint work with Xiaorui Sun and Shang-Hua Teng.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/