In this work we give a randomized blackbox polynomial identity testing (PIT) algorithm for constant-depth homogeneous noncommutative circuits, with poly-logarithmic time complexity in the circuit size. In fact, we show that the polynomial computable by such a depth-$(\Delta-1)$ circuit of size $s$ cannot be a polynomial identity for the $O(\log ... more >>>

We present a methodology for constructing interactive proof systems.
This methodology, which is implicit in prior works, consists of reducing the original claim to an iteratively generated sequence of claims such that each claim is (interactively) generated based on the prior claim.
Viewing each of these interactive generation ... more >>>

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetilde{\Theta}(M)$, ... more >>>