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
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
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
with Umang Bhaskar, Yu Cheng and Chaitanya Swamy
Download here
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
Published in SODA 2017
with Mark Braverman, Aviad Rubinstein and Omri Weinstein
Download here
Information Value of the Game
Published in ITCS 2018
with Mark Braverman
Download here
Semi-Direct Sum Theorem and Nearest Neighbor under l infinity
Published in APPROX/RANDOM 2018
with Mark Braverman
Download here
An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks
Published in FOCS 2020
with Omri Weinstein
Download here
On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
Published in ICALP 2026
with Jeremy Ahrens Huang and Chunhao Wang
Download here
CAMP: Coreset Accelerated Metacell Partitioning enables scalable analysis of single-cell data
Published in RECOMB 2026 (bioinformatics)
with Danrong Li and Stefan Canzar
Download here
An Ω( (log n / log log n)^2 ) Cell-Probe Lower Bound for Dynamic Boolean Data Structures
Published in FOCS 2026 (to appear)
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
CMPSC 464: Introduction to Theory of Computation
Undergraduate course, Penn State, CMPSC 464
Regular offering of CMPSC 464: Introduction to Theory of Computation. Offered Fall 2021, Fall 2022, Fall 2024, Spring 2027 (tentative).
CMPSC 497: Mathematical Tools in Computer Science
Undergraduate course, Penn State, CMPSC 497
Mathematical Tools in Computer Science, an undergraduate course at Penn State. Offered Spring 2024, Fall 2025
CSE 597: Advanced Communication Complexity
Graduate course, Penn State, CSE 597
Advanced topics in communication complexity for graduate students. Offered Spring 2026, Fall 2026 (tentative)