Author

Zhao Song

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $\epsilon$ using $O(\sqrt n\log^{13}m\cdot\log(mU/\epsilon))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagona...

Zhao Song · 0 citations

Preprint Sep 2026

An $n^{8/5+o(1)}$-Time $\Omega(\lambda^3)$-Approximation for Longest Common Subsequence

Let $\lambda$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $\Omega(\lambda^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}...

Zhao Song · 0 citations