Kasper Høgh

PPAD-Membership for Problems With Exact Rational Solutions: A General Approach via Convex Optimization

Abstract. We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problems with polynomial-time verifiable solutions. In particular, we construct a “pseudogate,” c...