Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Name thesis:degree_name
- Master
- Department dc:contributor.department
- Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
- Grantor dc:publisher
- Massachusetts Institute of Technology
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kwon, Sophia Seoyoung
- Advisor dc:contributor.advisor
-
- Williams, R. Ryan
Rights
dc:rights- Statement dc:rights
-
- In Copyright - Educational Use Permitted
- Copyright retained by author(s)
- Licence dc:rights.uri
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1721.1/151533
- OAI identifier oai:identifier
- oai:dspace.mit.edu:1721.1/151533