Research proof index

On the 1D Hilbert space, the optimal hypothesis testing rate is simply 1 - ε, since there's nothing to learn. (More generally this would hold whenever ρ=σ.) -

When the allowed Type I error ε is less than 1 (so, we have some limit on our errors), and the kernel of the state ρ contains the kernel of some element in S, then the optimal hypothesis rate is positive - there is some lower bound on the type II errors we'll see. In other words, under these conditions, we cannot completely avoid type II errors.

The polynomial Freiman-Ruzsa (PFR) conjecture: if A is a subset of an elementary abelian 2-group of doubling constant at most K, then A can be covered by at most 2 * K ^ 12 cosets of a subgroup of cardinality at most |A|.

Improved polynomial Freiman-Ruzsa theorem. Let $A$ be a nonempty subset of a finite elementary abelian $2$-group. If $|A+A|\le K|A|$, then there are a subspace $H$ and a set of representatives $c$ such that $A\subseteq c+H$, $|c|<2K^{11}$, and $|H|\le|A|$.

Improved polynomial Freiman-Ruzsa theorem without a finite ambient-group assumption. Let $A$ be a nonempty finite subset of an elementary abelian $2$-group. If $|A+A|\le K|A|$, then there are a finite subspace $H$ and a finite set $c$ such that $A\subseteq c+H$, $|c|<2K^{11}$, and $|H|\le|A|$.

Polynomial Freiman-Ruzsa theorem without a finite ambient-group assumption. Let $A$ be a nonempty finite subset of an elementary abelian $2$-group. If $|A+A|\le K|A|$, then there are a finite subspace $H$ and a finite set $c$ such that $A\subseteq c+H$, $|c|<2K^{12}$, and $|H|\le|A|$.