Editing Open Problems:57
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 4: | Line 4: | ||
}} | }} | ||
Consider the problem of “codeword testing” in the data stream model. In particular, consider a code | Consider the problem of “codeword testing” in the data stream model. In particular, consider a code | ||
| − | + | \[C:\Sigma^k\rightarrow\Sigma^n,\] | |
| − | with distance | + | with distance $d$. Recall that the distance of a code $C$ is the minimum Hamming distance between any two codewords, i.e., $\min_{\mathbb{x}\neq \mathbb{y}\in\Sigma^k} |\{i\in [n]| C(\mathbb{x})_i\neq C(\mathbb{y})_i\}|$. The specific problem is the following |
| − | + | The input to the problem is a vector $\mathbb{y}\in\Sigma^n$ and integer parameters $0\le \tau_1<\tau_2\le n$. The algorithm has to decide whether | |
| − | \[\Delta(\mathbb{y},C)\le \tau_1~ \mathrm{ or }~ \Delta(\mathbb{y},C)\geq \tau_2 | + | \[\Delta(\mathbb{y},C)\le \tau_1~ \mathrm{ or }~ \Delta(\mathbb{y},C)\geq \tau_2.\] |
| − | + | $\Delta(\mathbb{y},C)$ is the Hamming distance of $\mathbb{y}$ from the closest codeword in $C$. | |
Ideally, we want a one-pass, $\log^{O(1)}{n}$ space algorithm to solve the problem above for some ''good'' code $C$ (that is, we have $k\ge \Omega(n)$ and $d\ge \Omega(n)$). Or if we prove a hardness result, one would like a hardness result for ''every'' good code $C$. (For the sake of simplicity, assume that the algorithm has access to some succinct description of the code $C$.) | Ideally, we want a one-pass, $\log^{O(1)}{n}$ space algorithm to solve the problem above for some ''good'' code $C$ (that is, we have $k\ge \Omega(n)$ and $d\ge \Omega(n)$). Or if we prove a hardness result, one would like a hardness result for ''every'' good code $C$. (For the sake of simplicity, assume that the algorithm has access to some succinct description of the code $C$.) | ||
| Line 16: | Line 16: | ||
One of the original motivation (in {{cite|RudraU-10}}) for the study of the data-streaming version of the question was possibly to use communication complexity results to prove the impossibility of good locally testable codes. | One of the original motivation (in {{cite|RudraU-10}}) for the study of the data-streaming version of the question was possibly to use communication complexity results to prove the impossibility of good locally testable codes. | ||
| − | It was shown in {{cite|RudraU-10}} that for the well-known Reed-Solomon codes, the data stream version of the problem can be solved for $\tau_1=0$ and $\tau_2=1$ with one pass and logarithmic space. It can also be shown that the classical Berlekamp-Massey algorithm for decoding Reed-Solomon codes implies a solution for the case $\tau_2=\tau_1+1$ with one pass and space $\tilde{O}(\tau_1)$ | + | It was shown in {{cite|RudraU-10}} that for the well-known Reed-Solomon codes, the data stream version of the problem can be solved for $\tau_1=0$ and $\tau_2=1$ with one pass and logarithmic space. It can also be shown that the classical Berlekamp-Massey algorithm for decoding Reed-Solomon codes implies a solution for the case $\tau_2=\tau_1+1$ with one pass and space $\tilde{O}(\tau_1)$. (There is a small catch: the algorithm actually computes the location of errors ''if'' the number of errors is at most $\tau_1$. However, results in {{cite|RudraU-10}} can be used to verify if the returned error locations are indeed correct.) |
| + | |||
Finally, {{cite|McGregorRU-11}} showed how to solve this problem in one pass and $O(k\log{n})$ space. | Finally, {{cite|McGregorRU-11}} showed how to solve this problem in one pass and $O(k\log{n})$ space. | ||
This question is wide open: | This question is wide open: | ||
| − | + | Solve the problem above with one pass and $\tilde{O}(\min(k,\tau_1))$ space. | |
In fact the very special case of the problem above for $k=\tau_1=\sqrt{n}$ with one pass and space $o(\sqrt{n})$ is also open. This is open even for the special case of Reed-Solomon codes. | In fact the very special case of the problem above for $k=\tau_1=\sqrt{n}$ with one pass and space $o(\sqrt{n})$ is also open. This is open even for the special case of Reed-Solomon codes. | ||
| − | |||
| − | |||
| − | |||
