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

Sudan, Trevisan and Vadhan.

enter image description here (The formulation is taken from Shuichi Hirahara's paper.)

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.

  • $\begingroup$ 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. $\endgroup$
    – Or Meir
    Commented Oct 20, 2022 at 21:29
  • $\begingroup$ @OrMeir Inupts are strings $x$. The algorithm works correctly on input $x$ if it works for $r=Enc(x)$. $\endgroup$ Commented Oct 21, 2022 at 3:05

1 Answer 1


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)$).

  • $\begingroup$ 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$ $\endgroup$ Commented Oct 21, 2022 at 8:21

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.