Hyperdeterminants are high dimensional analogues of determinants, associated with tensors of formats generalizing square matrices. First conceived for $2\times 2\times 2$ tensors by Cayley, they were developed in generality by Gelfand, Kapranov and Zelevinsky. Yet, hyperdeterminants in three or more dimensions are long conjectured to be VNP-Hard to compute, akin ... more >>>

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ ... more >>>

We consider the query complexity of testing whether a bounded-degree graph is expanding, regardless of whether or not it is connected.

Whereas prior work studied testing the property of being an expander (equiv., testing the set of expander graphs), here we study testing the set of graphs that consist of ... more >>>