AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider several standard graph parameters aiming to design isomorphism tests where the exponent of the running time has only a polylogarithmic dependence on the parameter in question. Towards this end, we generalize the techniques developed for a recent isomorphism test for graphs of maximum degree d running in time n^{polylog(d)}. One consequence of this generalization is an isomorphism test for graphs of genus g running in time n^{polylog(g)}. In combination with recent results due to Wiebking, which combine the group-theoretic advances of Babai's quasipolynomial time isomorphism test with graph decomposition approaches, this even results in an isomorphism test running in time n^{polylog(h)} whenever the input graphs excludes an arbitrary h-vertex graphs as a minor.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

--email hidden

passcode not visible

logged in users only

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.