Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In ... more >>>

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies
\[
\omega^*(G^{\otimes n})
\le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n))
\]
for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen ... more >>>

We give a randomized algorithmic version of the Balog--Szemer\'edi--Gowers theorem for sets of integers. Let $A\subseteq[N]$ have size $n:=|A|\geq2$, let $1\leq K\leq n$, and suppose that its additive energy satisfies $E(A)\geq n^3/K$. Reiher and Schoen proved existentially that, for every fixed $\epsilon \in (0,1/2)$, there is a subset $A'\subseteq A$ ... more >>>

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, ... more >>>

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>