Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $\Theta(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, ... more >>>

The linear problem specified by an $n \times n$ matrix $M$ over a finite field is the problem of computing the product of $M$ and a given vector $x$. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit ... more >>>

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $\Omega((\log n / \log\log n)^2)$ for the Multiphase Problem of Patrascu [STOC 2010] (instantiated with Inner Product over $\mathbb{F}_2$). This matches the celebrated barrier for weighted problems established by Larsen [STOC 2012] ... more >>>