Toward improved non-interactive proof systems
The study of non-interactive proof systems, such as Merlin-Arthur proof systems and probabilistically checkable proofs, can yield insights into problems for which we do not yet have efficient algorithms. This work compiles many recent results in improved non-interactive proof systems–primarily Merli...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151533 |
| _version_ | 1826198571425202176 |
|---|---|
| author | Kwon, Sophia Seoyoung |
| author2 | Williams, R. Ryan |
| author_facet | Williams, R. Ryan Kwon, Sophia Seoyoung |
| author_sort | Kwon, Sophia Seoyoung |
| collection | MIT |
| description | The study of non-interactive proof systems, such as Merlin-Arthur proof systems and probabilistically checkable proofs, can yield insights into problems for which we do not yet have efficient algorithms. This work compiles many recent results in improved non-interactive proof systems–primarily Merlin-Arthur protocols for problems studied in the field of fine-grained complexity–and proposes a construction for interesting Merlin-Arthur protocols for any problem from an efficiently constructable PCP for the same. |
| first_indexed | 2024-09-23T11:06:58Z |
| format | Thesis |
| id | mit-1721.1/151533 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:06:58Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1515332023-08-01T03:57:29Z Toward improved non-interactive proof systems Kwon, Sophia Seoyoung Williams, R. Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The study of non-interactive proof systems, such as Merlin-Arthur proof systems and probabilistically checkable proofs, can yield insights into problems for which we do not yet have efficient algorithms. This work compiles many recent results in improved non-interactive proof systems–primarily Merlin-Arthur protocols for problems studied in the field of fine-grained complexity–and proposes a construction for interesting Merlin-Arthur protocols for any problem from an efficiently constructable PCP for the same. M.Eng. 2023-07-31T19:46:49Z 2023-07-31T19:46:49Z 2023-06 2023-06-06T16:35:08.444Z Thesis https://hdl.handle.net/1721.1/151533 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Kwon, Sophia Seoyoung Toward improved non-interactive proof systems |
| title | Toward improved non-interactive proof systems |
| title_full | Toward improved non-interactive proof systems |
| title_fullStr | Toward improved non-interactive proof systems |
| title_full_unstemmed | Toward improved non-interactive proof systems |
| title_short | Toward improved non-interactive proof systems |
| title_sort | toward improved non interactive proof systems |
| url | https://hdl.handle.net/1721.1/151533 |
| work_keys_str_mv | AT kwonsophiaseoyoung towardimprovednoninteractiveproofsystems |