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 >>>

A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH).
A ... more >>>