Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured ... more >>>

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