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: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/140059 |
| _version_ | 1811095431705264128 |
|---|---|
| author | Yang, Lisa L. |
| author2 | Vaikuntanathan, Vinod |
| author_facet | Vaikuntanathan, Vinod Yang, Lisa L. |
| author_sort | Yang, Lisa L. |
| collection | MIT |
| description | 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 quasi-polynomial hardness of this bilinear group assumption and any hard language that is decidable in quasi-polynomial time and polynomial space.
The delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration C' in T+1 steps. It is unambiguous meaning that it is hard to produce two different proofs for the same statement. |
| first_indexed | 2024-09-23T16:16:39Z |
| format | Thesis |
| id | mit-1721.1/140059 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:16:39Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1400592022-09-22T10:17:36Z Delegation with Updatable Unambiguous Proofs and PPAD-Hardness Yang, Lisa L. Vaikuntanathan, Vinod Kalai, Yael Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 quasi-polynomial hardness of this bilinear group assumption and any hard language that is decidable in quasi-polynomial time and polynomial space. The delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration C' in T+1 steps. It is unambiguous meaning that it is hard to produce two different proofs for the same statement. S.M. 2022-02-07T15:21:45Z 2022-02-07T15:21:45Z 2021-09 2021-09-21T19:54:13.671Z Thesis https://hdl.handle.net/1721.1/140059 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Yang, Lisa L. Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title | Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title_full | Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title_fullStr | Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title_full_unstemmed | Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title_short | Delegation with Updatable Unambiguous Proofs and PPAD-Hardness |
| title_sort | delegation with updatable unambiguous proofs and ppad hardness |
| url | https://hdl.handle.net/1721.1/140059 |
| work_keys_str_mv | AT yanglisal delegationwithupdatableunambiguousproofsandppadhardness |