Super-efficient rational proofs
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/93052 |
| _version_ | 1811072448072777728 |
|---|---|
| author | Azar, Pablo Daniel |
| author2 | Silvio Micali. |
| author_facet | Silvio Micali. Azar, Pablo Daniel |
| author_sort | Azar, Pablo Daniel |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. |
| first_indexed | 2024-09-23T09:06:07Z |
| format | Thesis |
| id | mit-1721.1/93052 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:06:07Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/930522019-04-10T20:45:39Z Super-efficient rational proofs Azar, Pablo Daniel Silvio Micali. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. Cataloged from PDF version of thesis. Includes bibliographical references (pages 47-49). Information asymmetry is a central problem in both computer science and economics. In many fundamental problems, an uninformed principal wants to obtain some knowledge from an untrusted expert. This models several real-world situations, such as a manager's relation with her employees, or the delegation of computational tasks to workers over the internet. Because the expert is untrusted, the principal needs some guarantee that the provided knowledge is correct. In computer science, this guarantee is usually provided via a proof, which the principal can verify. Thus, a dishonest expert will always get caught and penalized. In many economic settings, the guarantee that the knowledge is correct is usually provided via incentives. That is, a game is played between expert and principal such that the expert maximizes her utility by being honest. A rational proof is an interactive proof where the prover, Merlin, is neither honest nor malicious, but rational. That is, Merlin acts in order to maximize his own utility. I previously introduced and studied Rational Proofs when the verifier, Arthur, is a probabilistic polynomial-time machine [3]. In this thesis, I characterize super-efficient rational proofs, that is, rational proofs where Arthur runs in logarithmic time. These new rational proofs are very practical. Not only are they much faster than their classical analogues, but they also provide very tangible incentives for the expert to be honest. Arthur only needs a polynomial-size budget, yet he can penalize Merlin by a large quantity if he deviates from the truth. by Pablo Daniel Azar. Ph. D. 2015-01-20T17:58:09Z 2015-01-20T17:58:09Z 2014 2014 Thesis http://hdl.handle.net/1721.1/93052 899983827 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 49 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Azar, Pablo Daniel Super-efficient rational proofs |
| title | Super-efficient rational proofs |
| title_full | Super-efficient rational proofs |
| title_fullStr | Super-efficient rational proofs |
| title_full_unstemmed | Super-efficient rational proofs |
| title_short | Super-efficient rational proofs |
| title_sort | super efficient rational proofs |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/93052 |
| work_keys_str_mv | AT azarpablodaniel superefficientrationalproofs |