Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
In this work, we construct an updatable and unambiguous delegation scheme based on the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019]. Using this delegation scheme, we show PPAD-hardness (and hence the hardness of computing Nash equilibria) based on the qua...
Main Author: | Yang, Lisa L. |
---|---|
Other Authors: | Vaikuntanathan, Vinod |
Format: | Thesis |
Published: |
Massachusetts Institute of Technology
2022
|
Online Access: | https://hdl.handle.net/1721.1/140059 |
Similar Items
-
Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
by: Lombardi, Alex, et al.
Published: (2021) -
Pure-circuit: strong inapproximability for PPAD
by: Deligkas, A, et al.
Published: (2022) -
The Hairy Ball problem is PPAD-complete
by: Goldberg, P, et al.
Published: (2019) -
The Hairy Ball problem is PPAD-complete
by: Goldberg, PW, et al.
Published: (2021) -
Pure-Circuit: tight inapproximability for PPAD
by: Deligkas, A, et al.
Published: (2024)