Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time

Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams

In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in…