James Aisenberg (Theory Seminar)

Theory Seminar
"2-D Tucker is PPA complete"
James Aisenberg
Tuesday, November 24th, 2015, 1:00pm
EBU3B, Room 4258

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.

This talk is joint work with Maria Bonet and Sam Buss.