Skip navigation
Please use this identifier to cite or link to this item:
Title: Hardness Amplification in Two Prover Game and Communication Complexity
Authors: Ko, Young Kun
Advisors: Braverman, Mark
Contributors: Computer Science Department
Subjects: Computer science
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
Abstract: Whether repeating a task n-times in parallel amplifies the complexity measure in question by n-times is a key technical challenge in complexity theory. As a prelude to alternatives to parallel repetition, we investigate set-based repetition techniques. First we explore the applications of Birthday repetition, first introduced in [2] for quasi-polynomial time hardness results. These include hardness of computing best approximate Nash Equilibria in strategic bimatrix game [53], hardness of finding Densest k-subgraph [50] and hardness of obtaining best signaling scheme in zero-sum bayesian game [68]. From computational perspective, we first investigate the power and limits of parallel repetition of two-prover game [49]. We characterize the amortized behavior of the game via how much information one needs to win the game with good probability providing an intuitive explanation on why odd-cycle game introduced by [156] serves as a counterexample to strong parallel repetition. Then as an alternative to parallel repetition, we introduce symmetric parallel repetition, that is parallel repetition without coordinates. We show that symmetric parallel repetition indeed beats parallel repetition in some regimes and odd-cycle game is not a counterexample for symmetric parallel repetition. This sheds some light on possible attack route for infamous Unique Games Conjecture. From communication complexity perspective, we first tackle round tradeoff for Disjointness with Quantum communication. Then we introduce semi-direct sum as a mean to amplify hardness for asymmetric communication. As an application, we reprove and improve the lower bound for \ell_∞ approximate nearest neighbor search.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Ko_princeton_0181D_12775.pdf1.22 MBAdobe PDFView/Download

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