Showing 2026Show all
2 papers · 1 filter
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 , whose query distribution has the same support as the GHZ game (i.e., all satisfying ), the val…