Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings).

Lasse Wulf

Browse the full FOCS paper archive.