Young Kun Ko will present his PreFPO today, March 29, 2018 at 3:00 pm in CS402. Members of the Committee: Mark Braverman - Princeton University Omri Weinstein - Princeton University Gillat Kol - Princeton University Ran Raz - Princeton University Zeev Dvir - Princeton University All are welcomed to attend. Title : Hardness amplification for two prover game and communication complexity 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.
From computational perspective, we first investigate the power and limits of parallel repetition of two-prover games. 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 [Raz’07] serves as a counter-example to strong parallel repetition.
As an alternative to parallel repetition, we investigate set-based repetition techniques. First we explore the applications of Birthday repetition, first introduced in [AIM’14] for quasi-polynomial time hardness results. 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 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_\infty approximate nearest neighbor search.
Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University