Yang P. Liu

collaborators

3 papers

cs.DS2026

Streaming Complexity Separations for Dense and Sparse Graphs

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer +1

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dens…

cs.CC2026

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Kunal Mittal

We prove that for any 3-player game $G$ , whose query distribution has the same support as the GHZ game (i.e., all $x, y, z \in {0, 1}$ satisfying $x + y + z = 0 (mod 2)$ ), the val…

math.CO2025

Quasipolynomial bounds for the corners theorem

Michael Jaber, Yang P. Liu, Shachar Lovett +2

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G ∖ {0}$ such that $(x, y)$ …