(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.

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

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)$$).
• 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$ Commented Oct 21, 2022 at 8:21