Page Not Found
Page not found. Your pixels are in another canvas.
Sitemap
A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.
Pages
Young Kun Ko
About me
Page not in menu
This is a page not in th emain menu
Posts
publications
Approximating the best Nash Equilibrium in sub quasipolytime breaks the Exponential Time Hypothesis
Published in SODA 2015, 2015
with Mark Braverman and Omri Weinstein
Download here
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
Published in FOCS 2015, QIP 2016, Invited to SIAM Journal on Computing, 2015
with Mark Braverman, Ankit Garg, Jieming Mao and Dave Touchette
Download here
Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games
Published in EC 2016, 2016
with Umang Bhaskar, Yu Cheng and Chaitanya Swamy
Download here
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
Published in SODA 2017, 2017
with Mark Braverman, Aviad Rubinstein and Omri Weinstein
Download here
Information Value of the Game
Published in ITCS 2018, 2018
with Mark Braverman
Download here
Semi-Direct Sum Theorem and Nearest Neighbor under l infinity
Published in APPROX/RANDOM 2018, 2018
with Mark Braverman
Download here
An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks
Published in FOCS 2020, 2019
with Omri Weinstein
Download here
talks
Approximating the best Nash Equilibrium in sub-quasipolytime breaks the Exponential Time Hypothesis
Published:
Theory Lunch Talk on ETH-based Computational Lower Bound for finding Good Nash Equilibria in two player game.
Approximating the Best Nash Equilibrium in sub quasi polytime Breaks the Exponential Time Hypothesis
Published:
Conference Version of Nash Equilibrium Lower Bound Result.
Information Value of the Game
Published:
Conference Version of Information Value of the Game.
Semi-Direct Sum Theorem and Nearest Neighbor under l infinity.
Published:
Conference Version of Semi-Direct Sum Result
An Adaptive Step Toward the Multiphase Conjecture
Published:
In 2010, Patrascu proposed the Multiphase problem as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures, and showed it would imply unconditional lower bounds on many important dynamic data structure problems. After 10 years, there has been almost no progress on this conjecture. We show an ~\Omega(\sqrt{n}) cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but “layered” adaptivity. This captures all known set-intersection data structures and significantly strengthens previous Multiphase lower bounds, which only captured non-adaptive data structures. Our main technical result is a communication lower bound on a 4-party variant of Patrascu’s Number-On-Forehead game, using information complexity techniques.
teaching
Data Structure 2018 Fall
Undergraduate course, NYU, Courant, 2018
2018 Fall Data Structure course
Data Structure 2019 Spring
Undergraduate course, NYU, Courant, 2019
2019 Spring Data Structure course
Data Structure 2019 Fall
Undergraduate course, NYU, Courant, 2019
2019 Fall Data Structure course