James Aisenberg, Maria Luisa Bonet, Sam Buss
    "2-D Tucker is PPA Complete"
    Journal of Computer and System Sciences 108 (2020) 92-103.

    Download preprint.

Abstract: The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k-D Tucker for all k≥2. This corrects a claim in the literature that the Tucker search problem is in PPAD.

Back to Sam Buss's publications page.