Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective:
- The first family of natural ... more >>>

For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ that is free of restricted arithmetic progressions? We show that the ... more >>>

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>