Meeting notes 11 04 20

David R discussed his new problem for isomorphism of exponentially large graphs.

He began by describing the gadget description of Cai, Furer, Immerman optimal lower bound on the number of variables for graph identification. This is a construction that provides counter examples to the k-dimensional Weisfeiler-Leman example. In other words it provides sets of graphs for which the k dimensional WL algorithm will take exponential time to distinguish these graphs.

Using the motivation of the CFI constructions, David R asked some questions about distinguishing exponentially large graphs. In this model you can (say) query a vertex of an exponentially