<h3>Notation</h3>
<p>Let <span class="math-container">$\mathbb{F}$</span> be a finite field, and  <span class="math-container">$m, n$</span> be natural numbers.
An algorithm <span class="math-container">$A$</span> is said to have oracle access to a vector <span class="math-container">$v \in \mathbb{F}^n$</span> if it can query <span class="math-container">$v$</span> with input an index <span class="math-container">$i \in \{0, \dotsc, n-1\}$</span>, and receive as output the <span class="math-container">$i$</span>-th entry of <span class="math-container">$v$</span>, denoted <span class="math-container">$v[i]$</span>.</p>
<p>Two vectors <span class="math-container">$v_1, v_2 \in \mathbb{F}^n$</span> are said to have relative-Hamming distance of <span class="math-container">$\delta$</span> if they differ in a <span class="math-container">$\delta$</span>-fraction of locations. We denote this by <span class="math-container">$\Delta(v_1, v_2) = \delta$</span>, and say that <span class="math-container">$v_1$</span> is <span class="math-container">$\delta$</span>-far from <span class="math-container">$v_2$</span> (and vice versa)</p>
<h3>Problem statement</h3>
<p>Let <span class="math-container">$\varepsilon\in \mathbb{R}$</span> be such <span class="math-container">$0 \leq \varepsilon\leq 1$</span>. Then, design a probabilistic algorithm <span class="math-container">$A$</span> that, given oracle access to <span class="math-container">$m+1$</span> vectors <span class="math-container">$t, v_1, \dotsc, v_m \in \mathbb{F}^n$</span>, and given as explicit input <span class="math-container">$m$</span> field elements <span class="math-container">$a_1, \dotsc, a_m \in \mathbb{F}$</span>, decides whether <span class="math-container">$t$</span> is <span class="math-container">$\varepsilon$</span>-far from <span class="math-container">$s := \sum_{j=1}^m a_j v_j$</span> with error probability at most <span class="math-container">$1/3$</span>, that is:
<span class="math-container">$$
\Pr[A^{t, v_1, \dotsc, v_j}(a_1, \dotsc, a_m) = 1\  \text{and} \ \Delta(t, s) &gt; \varepsilon] &lt; \frac{1}{3}
$$</span></p>
<p>(Here <span class="math-container">$1/3$</span> is just a placeholder; any constant probability bounded away from <span class="math-container">$1$</span> suffices.)</p>
<h3>Preliminary result</h3>
<p>The following &quot;trivial&quot; algorithm achieves a constant error probability with <span class="math-container">$O(\frac{m}{|\log(1-\varepsilon)|}) \approx O(m/\varepsilon)$</span> queries.</p>
<p><span class="math-container">$A^{t, v_1, \dotsc, v_j}(a_1, \dotsc, a_m)$</span>: Repeat the following steps <span class="math-container">$1/\varepsilon$</span> times, and output <span class="math-container">$1$</span> if all checks pass:</p>
<ol>
<li>Sample an index <span class="math-container">$i$</span> uniformly at random from <span class="math-container">$\{0, \dotsc, n - 1\}$</span>.</li>
<li>Query <span class="math-container">$t, v_1, \dotsc, v_j$</span> at <span class="math-container">$i$</span> to obtain <span class="math-container">$t[i], v_1[i], \dotsc, v_j[i]$</span>.</li>
<li>Check that <span class="math-container">$t[i] = \sum_{j=1}^m a_j v_j[i]$</span>. If the check fails, halt and output <span class="math-container">$0$</span>. Otherwise, continue.</li>
</ol>
<p>It is straightforward to see that if <span class="math-container">$t$</span> is at least <span class="math-container">$\varepsilon$</span>-far from <span class="math-container">$s$</span>, then at each step, the check will pass with probability at most <span class="math-container">$1 - \varepsilon$</span>. Thus the algorithm will output <span class="math-container">$1$</span> with probability <span class="math-container">$(1 - \varepsilon)^{1/\varepsilon} &lt; e^{-1} \approx 1/3$</span>. Furthermore, the algorithm clearly makes a total of <span class="math-container">$(m+1) \cdot \frac{1}{\varepsilon}$</span> queries.</p>
<p>Can one design an algorithm with better query complexity? I would also be interested in seeing an interactive (oracle) proof of proximity for this problem.</p>

CC BY-SA 4.0
2023-04-19T13:24:55.313Z
I must be misunderstanding something - why is an $\Omega(1/\delta)$ lower bound not immediate (which would prove your upper bound is tight)?
Clement C.
CC BY-SA 4.0
2023-04-21T03:42:19.477Z
@ClementC., could you provide some pointers on how to go about deriving the lower bound? Also you are right that it should $m$ times what I had stated previously. I've edited the question to correct this.
Pratyush Mishra
CC BY-SA 4.0
2023-04-24T20:41:07.230Z
Your algorithm seems to imply it is a promise problem: either $t=s$ or $\Delta(t,s)>\epsilon$. Is this the case? If you want to distinguish $\Delta(t,s)>\epsilon$ from $\Delta(t,s)\leq \epsilon$, I'm pretty sure the query complexity scales with $n$.
lamontap
<interactive-proofs><property-testing>
Property testing for membership in span of vectors
Pratyush Mishra
# Property testing for membership in span of vectors

(Asked by: username_0 on 2023-04-18)

### Notation

Let $\mathbb{F}$ be a finite field, and $m, n$ be natural numbers.
An algorithm $A$ is said to have oracle access to a vector $v \in \mathbb{F}^n$ if it can query $v$ with input an index $i \in \{0, \dotsc, n-1\}$, and receive as output the $i$-th entry of $v$, denoted $v[i]$.

Two vectors $v\_1, v\_2 \in \mathbb{F}^n$ are said to have relative-Hamming distance of $\delta$ if they differ in a $\delta$-fraction of locations. We denote this by $\Delta(v\_1, v\_2) = \delta$, and say that $v\_1$ is $\delta$-far from $v\_2$ (and vice versa)

### Problem statement

Let $\varepsilon\in \mathbb{R}$ be such $0 \leq \varepsilon\leq 1$. Then, design a probabilistic algorithm $A$ that, given oracle access to $m+1$ vectors $t, v\_1, \dotsc, v\_m \in \mathbb{F}^n$, and given as explicit input $m$ field elements $a\_1, \dotsc, a\_m \in \mathbb{F}$, decides whether $t$ is $\varepsilon$-far from $s := \sum\_{j=1}^m a\_j v\_j$ with error probability at most $1/3$, that is:
$$
\Pr[A^{t, v\_1, \dotsc, v\_j}(a\_1, \dotsc, a\_m) = 1\ \text{and} \ \Delta(t, s) > \varepsilon] < \frac{1}{3}
$$

(Here $1/3$ is just a placeholder; any constant probability bounded away from $1$ suffices.)

### Preliminary result

The following "trivial" algorithm achieves a constant error probability with $O(\frac{m}{|\log(1-\varepsilon)|}) \approx O(m/\varepsilon)$ queries.

$A^{t, v\_1, \dotsc, v\_j}(a\_1, \dotsc, a\_m)$: Repeat the following steps $1/\varepsilon$ times, and output $1$ if all checks pass:

1. Sample an index $i$ uniformly at random from $\{0, \dotsc, n - 1\}$.
2. Query $t, v\_1, \dotsc, v\_j$ at $i$ to obtain $t[i], v\_1[i], \dotsc, v\_j[i]$.
3. Check that $t[i] = \sum\_{j=1}^m a\_j v\_j[i]$. If the check fails, halt and output $0$. Otherwise, continue.

It is straightforward to see that if $t$ is at least $\varepsilon$-far from $s$, then at each step, the check will pass with probability at most $1 - \varepsilon$. Thus the algorithm will output $1$ with probability $(1 - \varepsilon)^{1/\varepsilon} < e^{-1} \approx 1/3$. Furthermore, the algorithm clearly makes a total of $(m+1) \cdot \frac{1}{\varepsilon}$ queries.

Can one design an algorithm with better query complexity? I would also be interested in seeing an interactive (oracle) proof of proximity for this problem.

**Tags:** interactive-proofs, property-testing

> **Comments:**
> **username_1**: I must be misunderstanding something - why is an $\Omega(1/\delta)$ lower bound not immediate (which would prove your upper bound is tight)?  
> **username_0**: @ClementC., could you provide some pointers on how to go about deriving the lower bound? Also you are right that it should $m$ times what I had stated previously. I've edited the question to correct this.  
> **username_2**: Your algorithm seems to imply it is a promise problem: either $t=s$ or $\Delta(t,s)>\epsilon$. Is this the case? If you want to distinguish $\Delta(t,s)>\epsilon$ from $\Delta(t,s)\leq \epsilon$, I'm pretty sure the query complexity scales with $n$.  

---

## 0 answers

