Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-163 | 11th October 2015 06:45

2-D Tucker is PPA complete

RSS-Feed




TR15-163
Authors: James Aisenberg, Maria Luisa Bonet, Sam Buss
Publication: 11th October 2015 07:35
Downloads: 850
Keywords: 


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\ge 2$. This corrects a claim in the literature that the Tucker search problem is in PPAD.



ISSN 1433-8092 | Imprint