The Orthogonal Vectors Problem (OV$_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a \in A$ and $b \in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\varepsilon > 0$, ... more >>>

For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in ... more >>>

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the ... more >>>