[talks] 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.

[Nicki Gotsis]

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. 

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). 

A copy of his thesis is available in CS 310. All are welcome to attend. 

Abstract follows below. 


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 �∞ approximate nearest neighbor search. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20180914/a92de97b/attachment.html>