Chi-Ning Chou

activity

20182022

most citedLimitations of Linear Cross-Entropy as a Measure for Quantum Advantage

43 citations · 99 across the 11 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2018

Tracking the $ℓ_{2}$ Norm with Constant Update Time

Chi-Ning Chou, Zhixian Lei, Preetum Nakkiran

The \emph{ $ℓ_{2}$ tracking problem} is the task of obtaining a streaming algorithm that, given access to a stream of items $a_{1}, a_{2}, a_{3}, \dots$ from a universe $[n]$ , outputs at e…

cs.DS2018★ 40 cited

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

Boaz Barak, Chi-Ning Chou, Zhixian Lei +2

We give a quasipolynomial time algorithm for the graph matching problem (also known as noisy or robust graph isomorphism) on correlated random graphs. Specifically, for every $γ > 0$ …

Tracking the ℓ2​ Norm with Constant Update Time

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

Tracking the $ℓ_{2}$ Norm with Constant Update Time