<p>Unfortunately, constructing such a tester appears to be hard: at least as hard as the <a href="https://en.wikipedia.org/wiki/Parity_learning" rel="nofollow noreferrer">learning parity with noise</a> (LPN) problem.</p>
<p>Without loss of generality, we can focus on the problem of determining whether there is a rank-<span class="math-container">$n-1$</span> linear subspace <span class="math-container">$L$</span> such that <span class="math-container">$P$</span> is concentrated on <span class="math-container">$L$</span>. (This is wlog because every linear subspace is contained within some rank-<span class="math-container">$n-1$</span> linear subspace.) This is equivalent to testing whether there exists <span class="math-container">$w$</span> such that <span class="math-container">$\Pr_{x \sim P}[w \cdot x = 0] \ge 1-\epsilon$</span>.  That is the LPN problem.  I <em>think</em> LPN is believed to remain hard even if the noise <span class="math-container">$\epsilon$</span> is small though I am not absolutely certain about that.</p>
<p>In contrast, if you have ability not just to sample from <span class="math-container">$P$</span>, but also ability to compute <span class="math-container">$P(x)$</span> for any <span class="math-container">$x$</span>, then the problem can be solved in polynomial time by using the Goldreich-Levin algorithm to reconstruct such a <span class="math-container">$w$</span>.</p>

CC BY-SA 4.0
2024-03-27T03:35:56.233Z
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
Command Master
CC BY-SA 4.0
2024-03-27T04:04:17.770Z
@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!
D.W.
CC BY-SA 4.0
2024-03-27T13:43:47.503Z
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.
Marsl
CC BY-SA 4.0
2024-03-27T22:58:18.363Z
@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.
D.W.
CC BY-SA 4.0
2024-03-26T22:02:56.607Z
2024-03-26T22:02:56.607Z
D.W.
<p>Let <span class="math-container">$P$</span> be a distribution over n-bitstrings which we will view as elements of <span class="math-container">$\mathbb{F}_2^n$</span>. Given sample access to <span class="math-container">$P$</span>, I am looking for an algorithm that tests if <span class="math-container">$P$</span> is heavily concentrated on a proper linear subspace <span class="math-container">$L$</span>. That is, I want to test if there exists a subspace <span class="math-container">$L \subsetneq \mathbb{F}_2^n $</span> such that <span class="math-container">$P(L) = \sum_{x\in L} P(x) \geq 1-\epsilon$</span> for a given small <span class="math-container">$\epsilon$</span>.</p>
<p>I guess a different formulation of my question is: I am looking for a tolerant tester for the property of <span class="math-container">$P$</span> being confined to some proper linear subspace <span class="math-container">$L$</span> of <span class="math-container">$\mathbb{F}_2^n$</span>.</p>
<p>I know that for a non-tolerant test, corresponding to <span class="math-container">$\epsilon=0$</span> above, I can take <span class="math-container">$K=O(n)$</span> many samples <span class="math-container">$x_1, \dots, x_K$</span> and compute the rank of the matrix (over <span class="math-container">$\mathbb{F}_2$</span>) formed by the samples in order to check if they span all of <span class="math-container">$\mathbb{F}_2^n$</span> and this will test the property with high probability over the samples.</p>
<p>However, for a small constant <span class="math-container">$\epsilon$</span>, this &quot;rank-test&quot; is not tolerant. To see this, consider that the test is taking <span class="math-container">$O(n)$</span> many samples, so there are <span class="math-container">$O(n)$</span> chances to land outside the subspace and so this &quot;rank-test&quot; will only be tolerant for <span class="math-container">$\epsilon = O(1/n)$</span>. So, in some sense this test is too sensitive, however since I am working over <span class="math-container">$\mathbb{F}_2$</span>, there seem to be no good relaxations of the rank function.</p>
<p>I would be happy for any ideas, pointers, related problems.</p>

<coding-theory><property-testing>
Testing if a distribution over $\mathbb{F}_2^n$ is heavily supported on a subspace
Marsl
# Testing if a distribution over $\mathbb{F}_2^n$ is heavily supported on a subspace

(Asked by: username_0 on 2024-03-26)

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.

**Tags:** coding-theory, property-testing

---

## 1 answers

### Answer by username_1 on 2024-03-26. Score: 3 | Accepted answer

Unfortunately, constructing such a tester appears to be hard: at least as hard as the [learning parity with noise](https://en.wikipedia.org/wiki/Parity_learning) (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$.

> **Comments:**
> **username_2**: 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  
> **username_1**: @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!  
> **username_0**: 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.  
> **username_1**: @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.  

---

