Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"parallel repetition"”.
-
Concentration Bounds from Parallel Repetition Theorems
This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: - A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all …
-
Parallel Repetition of Prover-Verifier Quantum Interactions
… behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible …
-
DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY
… theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel …
-
Quantum Information and Variants of Interactive Proof Systems
… reduction technique of such proof systems via parallel repetition. The question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. (1) We show that the expressive power of quantum interactive proof systems is …
-
Extended Nonlocal Games
… a standard quantum strategy. We also analyze the parallel repetition of monogamy-of-entanglement games; the study of how a game performs when there are multiple instances of the game played independently. We find that certain classes of monogamy-of-entanglement games obey strong parallel …
-
Studies in Models of Quantum Proof Systems
… games with shared entanglement. We show a parallel repetition theorem for the entangled value of any two-player one-round game, where the questions to the players are drawn independently.
-
Distributional Security for OWF, PRF and Garbling
… OWF. The simplest such construction is through parallel repetition, due to Yao [40]. In this thesis, we first study which input distributions to such parallel repetition of a weak OWF can yield a OWF. We show a lower bound on the entropy that the input needs to have. We also study input …
-
Approximation, Proof Systems, and Correlations in a Quantum World
… an alternate proof that SepQMA(m) admits perfect parallel repetition. This proof is novel in that it utilizes cone programming duality. Our final area of study concerns non-classical correlations in quantum systems. Specifically, there exist genuinely quantum correlations beyond entanglement in …