2 papers
cs.CC2015
Undirected Cat-and-Mouse is P-complete
Arefin Huq
Cat-and-mouse is a two-player game on a finite graph. Chandra and Stockmeyer showed cat-and-mouse is P-complete on directed graphs. We show cat-and-mouse is P-complete on undirecte…
cs.CC2015
The matching problem has no small symmetric SDP
Gábor Braun, Jonah Brown-Cohen, Arefin Huq +5
Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß recently proved that any, not necessarily symmetric, linear program also has exp…