Skip to main content

Toward probabilistic checking against non-signaling strategies with constant locality

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2021-06-30
Authors/Contributors
Abstract
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this thesis we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.
Document
Identifier
etd21437
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Shinkar, Igor
Language
English
Member of collection
Download file Size
input_data\21653\etd21437.pdf 584.45 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 2