<html><body><div id="zimbraEditorContainer" style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000" class="10"><div></div><div data-marker="__QUOTED_TEXT__"><p>
Young Kun Ko will present his FPO "Hardness Amplification in Two Prover Game and Communication Complexity" on Monday, 9/17/2018 at 1pm in CS 401.</p><p>The members of his committee are as follows: Mark Braverman (Adviser); Omri Weinstein (Columbia University) and Gillat Kol (Readers); Zeev Dvir and Ran Raz (Examiners).</p><p>A copy of his thesis is available in CS 310. All are welcome to attend.</p><p>Abstract follows below.</p>
<p></p><div data-marker="__QUOTED_TEXT__">Whether repeating a task n-times in parallel amplifies the complexity measure in question</div><div data-marker="__QUOTED_TEXT__">by n-times is a key technical challenge in complexity theory.</div><div data-marker="__QUOTED_TEXT__">As a prelude to alternatives to parallel repetition, we investigate set-based repetition</div><div data-marker="__QUOTED_TEXT__">techniques. First we explore the applications of Birthday repetition, first introduced in [2]</div><div data-marker="__QUOTED_TEXT__">for quasi-polynomial time hardness results. These include hardness of computing best</div><div data-marker="__QUOTED_TEXT__">approximate Nash Equilibria in strategic bimatrix game [53], hardness of finding Densest</div><div data-marker="__QUOTED_TEXT__">k-subgraph [50] and hardness of obtaining best signaling scheme in zero-sum bayesian</div><div data-marker="__QUOTED_TEXT__">game [68].</div><div data-marker="__QUOTED_TEXT__">From computational perspective, we first investigate the power and limits of parallel</div><div data-marker="__QUOTED_TEXT__">repetition of two-prover game [49]. We characterize the amortized behavior of the game</div><div data-marker="__QUOTED_TEXT__">via how much information one needs to win the game with good probability providing</div><div data-marker="__QUOTED_TEXT__">an intuitive explanation on why odd-cycle game introduced by [156] serves as a counterexample</div><div data-marker="__QUOTED_TEXT__">to strong parallel repetition.</div><div data-marker="__QUOTED_TEXT__">Then as an alternative to parallel repetition, we introduce symmetric parallel repetition,</div><div data-marker="__QUOTED_TEXT__">that is parallel repetition without coordinates. We show that symmetric parallel</div><div data-marker="__QUOTED_TEXT__">repetition indeed beats parallel repetition in some regimes and odd-cycle game is not</div><div data-marker="__QUOTED_TEXT__">a counterexample for symmetric parallel repetition. This sheds some light on possible</div><div data-marker="__QUOTED_TEXT__">attack route for infamous Unique Games Conjecture.</div><div data-marker="__QUOTED_TEXT__">From communication complexity perspective, we first tackle round tradeoff for Disjointness</div><div data-marker="__QUOTED_TEXT__">with Quantum communication. Then we introduce semi-direct sum as a mean</div><div data-marker="__QUOTED_TEXT__">to amplify hardness for asymmetric communication. As an application, we reprove and</div><div data-marker="__QUOTED_TEXT__">improve the lower bound for �∞ approximate nearest neighbor search.</div></div></div></body></html>