Refuting Perfect Matchings in Spectral Expanders is Hard

Ari Biswas, Rajko Nenadov

This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Sq…