3
$\begingroup$

Let $P$ be a distribution over n-bitstrings which we will view as elements of $\mathbb{F}_2^n$. Given sample access to $P$, I am looking for an algorithm that tests if $P$ is heavily concentrated on a proper linear subspace $L$. That is, I want to test if there exists a subspace $L \subsetneq \mathbb{F}_2^n $ such that $P(L) = \sum_{x\in L} P(x) \geq 1-\epsilon$ for a given small $\epsilon$.

I guess a different formulation of my question is: I am looking for a tolerant tester for the property of $P$ being confined to some proper linear subspace $L$ of $\mathbb{F}_2^n$.

I know that for a non-tolerant test, corresponding to $\epsilon=0$ above, I can take $K=O(n)$ many samples $x_1, \dots, x_K$ and compute the rank of the matrix (over $\mathbb{F}_2$) formed by the samples in order to check if they span all of $\mathbb{F}_2^n$ and this will test the property with high probability over the samples.

However, for a small constant $\epsilon$, this "rank-test" is not tolerant. To see this, consider that the test is taking $O(n)$ many samples, so there are $O(n)$ chances to land outside the subspace and so this "rank-test" will only be tolerant for $\epsilon = O(1/n)$. So, in some sense this test is too sensitive, however since I am working over $\mathbb{F}_2$, there seem to be no good relaxations of the rank function.

I would be happy for any ideas, pointers, related problems.

$\endgroup$

1 Answer 1

3
$\begingroup$

Unfortunately, constructing such a tester appears to be hard: at least as hard as the learning parity with noise (LPN) problem.

Without loss of generality, we can focus on the problem of determining whether there is a rank-$n-1$ linear subspace $L$ such that $P$ is concentrated on $L$. (This is wlog because every linear subspace is contained within some rank-$n-1$ linear subspace.) This is equivalent to testing whether there exists $w$ such that $\Pr_{x \sim P}[w \cdot x = 0] \ge 1-\epsilon$. That is the LPN problem. I think LPN is believed to remain hard even if the noise $\epsilon$ is small though I am not absolutely certain about that.

In contrast, if you have ability not just to sample from $P$, but also ability to compute $P(x)$ for any $x$, then the problem can be solved in polynomial time by using the Goldreich-Levin algorithm to reconstruct such a $w$.

$\endgroup$
4
  • $\begingroup$ LPN also depends on the number of samples. Since we have as many samples as we want here, there might still be something which can be done $\endgroup$ Commented Mar 27 at 3:35
  • $\begingroup$ @CommandMaster, As far as I know, even with unlimited samples (well, polynomially many samples), LPN is believed/conjectured to not be solvable in polynomial time. I believe this extends even to the case where the noise $\epsilon$ is small. If there is something I'm missing, I'd love to learn about it! $\endgroup$
    – D.W.
    Commented Mar 27 at 4:04
  • $\begingroup$ Hi @D.W., thanks for your answer. I agree with what you wrote, so O(n/eps^2) should in principle be enough to test from a sample complexity point of view (just estimating subspace weight of all 2^n - 1 many (n-1)-dimensional subspaces?) but time complexity is probably an issue as you rightly point out. About the connection to LPN, I have a small question. I thought that in LPN the input distribution is usually the uniform distribution over bitstrings which is not the case here, so I am wondering if this could help somehow. $\endgroup$
    – Marsl
    Commented Mar 27 at 13:43
  • $\begingroup$ @Marsl, Yes, good point, my answer is focusing on time complexity rather than sample complexity. If it's hard for a special case (e.g., the uniform distribution), it's also hard for the general case (e.g., seeking a tester that works for all distributions), so I'm not seeing how it could help, but maybe you see something I'm missing. $\endgroup$
    – D.W.
    Commented Mar 27 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.