English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce a general technique for proving membership of search problemswith exact rational solutions in PPAD, one of the most well-known classescontaining total search problems with polynomial-time verifiable solutions. Inparticular, we construct a "pseudogate", coined the linear-OPT-gate, which canbe used as a "plug-and-play" component in a piecewise-linear (PL) arithmeticcircuit, as an integral component of the "Linear-FIXP" equivalent definition ofthe class. The linear-OPT-gate can solve several convex optimization programs,including quadratic programs, which often appear organically in the simplestexistence proofs for these problems. This effectively transforms existenceproofs to PPAD-membership proofs, and consequently establishes the existence ofsolutions described by rational numbers.  Using the linear-OPT-gate, we are able to significantly simplify andgeneralize almost all known PPAD-membership proofs for finding exact solutionsin the application domains of game theory, competitive markets, auto-biddingauctions, and fair division, as well as to obtain new PPAD-membership resultsfor problems in these domains.

PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization