Skip navigation
Please use this identifier to cite or link to this item:
Title: Communication Complexity With a Prover: Applications to Fine-Grain Complexity
Authors: Neyman, Eric
Advisors: Dvir, Zeev
Kol, Gillat
Department: Mathematics
Certificate Program: Applications of Computing Program
Class Year: 2019
Abstract: While the field of fine-grain complexity has been around for fifteen years, recent work has opened up new directions. A 2017 paper introduced a method for proving hardness results in P based on communication protocols in the Merlin-Arthur setting and probabilistically checkable proofs. A follow-up paper expanded on these techniques and used them to prove results based on hardness assumptions about the satisfiability of branching programs. We continue this line of work, specifically proving that under the assumption that the satisfiability of branching programs of linear size cannot be checked substantially faster than in time 2^n, the orthogonal vectors problem cannot be solved substantially faster than in quadratic time.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
NEYMAN-ERIC-THESIS.pdf474.55 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.