<p>I don't think Step 4 works.  The circuit <span class="math-container">$C_j^{\mathrm{Enc}(x)}$</span> takes <span class="math-container">$i \in [N]$</span> as input and outputs the <span class="math-container">$i$</span>-th bit of <span class="math-container">$x$</span>.  For each <span class="math-container">$i \in [N]$</span>, the circuit asks <span class="math-container">$\mathrm{poly}(\log N)$</span> queries to bits of <span class="math-container">$\mathrm{Enc}(x)$</span>, but the queries depend on <span class="math-container">$i$</span>.  In order to get a short list that contains <span class="math-container">$x$</span>, you need to answer all the queries for <em>every</em> <span class="math-container">$i \in [N]$</span>, which can be as many as <span class="math-container">$O(N \cdot \mathrm{poly}(\log N))$</span> in total (and cannot be bounded by <span class="math-container">$\mathrm{poly}(\log N)$</span>).</p>

CC BY-SA 4.0
2022-10-21T08:21:53.417Z
The circuit that I defined is not any $C_j$ from the theorem. It is a derandomization (not full, only for $x \in A$) of Dec that not depend on $i$
Alexey Milovanov
CC BY-SA 4.0
2022-10-21T05:53:24.887Z
2022-10-21T05:53:24.887Z
Shuichi
<p>My question is about the following result about list-decoding of</p>
<p><a href="https://doi.org/10.1006/jcss.2000.1730" rel="nofollow noreferrer">Sudan, Trevisan and Vadhan.</a></p>
<p><a href="https://i.sstatic.net/hgGUK.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hgGUK.jpg" alt="enter image description here" /></a>
(The formulation is taken from <a href="https://eccc.weizmann.ac.il/report/2020/050/" rel="nofollow noreferrer">Shuichi Hirahara's paper</a>.)</p>
<p>I do not understand how this is possible. I think this result contradicts to  a simple information  reasoning:</p>
<ol>
<li>Assume <span class="math-container">$\epsilon = \frac{1}{10}$</span> for example. Then the algorithm works in time  <span class="math-container">$\text{poly} (\log N)$</span> and the cardinality of list <span class="math-container">$L$</span> is <span class="math-container">$\text{poly} (\log N)$</span> too.</li>
<li>Fix some x and random bits. We say that the algorithm works correctly in this case if it works correctly (the output list contains <span class="math-container">$x$</span>) for <span class="math-container">$r=Enc(x)$</span>.</li>
<li>For some <span class="math-container">$N$</span> we can fix random bits of the decoding algorithm such that this algorithm is  transformed to a deterministic circuit <span class="math-container">$D$</span> that works correctly for most inputs. Denote by <span class="math-container">$A$</span> the set of ``good'' inputs; the cardinality of <span class="math-container">$A$</span> is greater than <span class="math-container">$2^{N-1}$</span>.</li>
<li>This circuit <span class="math-container">$D$</span> allows  by asking <span class="math-container">$\text{poly} (\log N)$</span> Yes/No questions to determine a string <span class="math-container">$x \in A$</span> : first, the circuit asks  <span class="math-container">$\text{poly} (\log N)$</span> such questions about bits of <span class="math-container">$Enc(x)$</span>; then circuit outputs  <span class="math-container">$\text{poly} (\log N)$</span>-list containing <span class="math-container">$x$</span> - now we need just <span class="math-container">$O(\log \log N)$</span>-bits to determine <span class="math-container">$x$</span>.</li>
<li>However, the yes/no-question algorithm above can determine only <span class="math-container">$2^{\text{poly} (\log N)}$</span> strings  that is much less then cardinality of <span class="math-container">$A$</span>.</li>
</ol>
<p>Why am I wrong?</p>
<p>UPD: I have understood. Circuits <span class="math-container">$C_j$</span> has access to <span class="math-container">$r$</span> so it is impossible to determine <span class="math-container">$x$</span> by my way. Sorry for the confusion.</p>

CC BY-SA 4.0
2022-10-20T21:29:17.243Z
When you say "works for most inputs" and "good inputs", what do you mean by "input"? Do you refer to the string $r$ or to the strings $x$ that are close to $r$?
If you refer to the strings $x$, then there are not so many such strings: for a fixed $r$, there are only $O(1)$ such $x$'s (for your choice of $\epsilon$).
If you refer to $r$, then I am not sure how you can determine it using a small number of yes/no questions.
Or Meir
CC BY-SA 4.0
2022-10-21T03:05:05.077Z
@OrMeir Inupts are strings $x$. The algorithm works correctly on input $x$ if it works for $r=Enc(x)$.
Alexey Milovanov
<coding-theory>
Theorem of Sudan, Trevisan and Vadhan about list-decoding
Alexey Milovanov
# Theorem of Sudan, Trevisan and Vadhan about list-decoding

(Asked by: username_0 on 2022-10-20)

My question is about the following result about list-decoding of

[Sudan, Trevisan and Vadhan.](https://doi.org/10.1006/jcss.2000.1730)

[![enter image description here](https://i.sstatic.net/hgGUK.jpg)](https://i.sstatic.net/hgGUK.jpg)
(The formulation is taken from [Shuichi Hirahara's paper](https://eccc.weizmann.ac.il/report/2020/050/).)

I do not understand how this is possible. I think this result contradicts to a simple information reasoning:

1. Assume $\epsilon = \frac{1}{10}$ for example. Then the algorithm works in time $\text{poly} (\log N)$ and the cardinality of list $L$ is $\text{poly} (\log N)$ too.
2. Fix some x and random bits. We say that the algorithm works correctly in this case if it works correctly (the output list contains $x$) for $r=Enc(x)$.
3. For some $N$ we can fix random bits of the decoding algorithm such that this algorithm is transformed to a deterministic circuit $D$ that works correctly for most inputs. Denote by $A$ the set of ``good'' inputs; the cardinality of $A$ is greater than $2^{N-1}$.
4. This circuit $D$ allows by asking $\text{poly} (\log N)$ Yes/No questions to determine a string $x \in A$ : first, the circuit asks $\text{poly} (\log N)$ such questions about bits of $Enc(x)$; then circuit outputs $\text{poly} (\log N)$-list containing $x$ - now we need just $O(\log \log N)$-bits to determine $x$.
5. However, the yes/no-question algorithm above can determine only $2^{\text{poly} (\log N)}$ strings that is much less then cardinality of $A$.

Why am I wrong?

UPD: I have understood. Circuits $C\_j$ has access to $r$ so it is impossible to determine $x$ by my way. Sorry for the confusion.

**Tags:** coding-theory
> **Comments:**
> **username_1**: When you say "works for most inputs" and "good inputs", what do you mean by "input"? Do you refer to the string $r$ or to the strings $x$ that are close to $r$? If you refer to the strings $x$, then there are not so many such strings: for a fixed $r$, there are only $O(1)$ such $x$'s (for your choice of $\epsilon$). If you refer to $r$, then I am not sure how you can determine it using a small number of yes/no questions.  
> **username_0**: @OrMeir Inupts are strings $x$. The algorithm works correctly on input $x$ if it works for $r=Enc(x)$.  

---

## 1 answers

### Answer by username_2 on 2022-10-21. Score: 3 | Accepted answer

I don't think Step 4 works. The circuit $C\_j^{\mathrm{Enc}(x)}$ takes $i \in [N]$ as input and outputs the $i$-th bit of $x$. For each $i \in [N]$, the circuit asks $\mathrm{poly}(\log N)$ queries to bits of $\mathrm{Enc}(x)$, but the queries depend on $i$. In order to get a short list that contains $x$, you need to answer all the queries for *every* $i \in [N]$, which can be as many as $O(N \cdot \mathrm{poly}(\log N))$ in total (and cannot be bounded by $\mathrm{poly}(\log N)$).

> **Comments:**
> **username_0**: The circuit that I defined is not any $C_j$ from the theorem. It is a derandomization (not full, only for $x \in A$) of Dec that not depend on $i$  

---

