Li 2023 two source extractors asymptotically optimal entropy

../

corollary_1_9: Li's strongly explicit graphs on N vertices with no clique or independent set of size log^c N, for a constant c > 1, derived from the two-source extractor for min-entropy c log n.

theorem_1_10: Li's explicit strong seeded non-malleable extractor with seed length C log(n/epsilon), entropy C log(d/epsilon) and output length (1 - gamma)k/2, which the paper calls asymptotically optimal.

theorem_1_11: Li's explicit two-source non-malleable extractor for a first source of entropy (2/3 + gamma)n and a second of min-entropy at least C log n, with error 2^{-Omega(k)} and output length Omega(k); its proof is sketched.

theorem_1_12: Li's explicit affine non-malleable extractor for affine sources of entropy (1 - gamma)n, for some constant gamma, with error 2^{-Omega(n)} and output length Omega(n).

theorem_1_13: Li's explicit two-round privacy amplification protocol against an active adversary, for any security parameter s at most alpha k, with entropy loss O(log log n + s) and communication complexity O(log n + s).

theorem_1_14: Li's non-malleable code against 2-split-state tampering, with efficient encoding and decoding, constant rate k/(2n) and error 2^{-Omega(k)}.

theorem_1_15: Li's non-malleable code against affine tampering of the whole codeword, with efficient encoding and decoding, constant rate k/n and error 2^{-Omega(k)}.

theorem_1_16: Li's explicit Boolean function, the sumset extractor, that requires strongly read-once linear branching programs of size 2^{n - O(log n)}.

theorem_1_6: Li's explicit one-bit extractor, with any constant error, for every interleaving of two independent n-bit sources of min-entropy at least c log n; the paper derives Corollary 1.9's Ramsey graphs from it.

theorem_1_7: Li's explicit one-bit extractor, with any constant error, for the sum of two independent n-bit sources of min-entropy at least c log n and for affine sources of entropy at least c log n.

theorem_1_8: Li's explicit one-bit extractor, with any constant error, for n-bit sources generated by width-2^s branching programs with min-entropy at least 2s + c log n.

theorem_6_2: Li's explicit two-source non-malleable extractor for two sources of min-entropy (1 - gamma)n, for some constant gamma, with error 2^{-Omega(n)}; the paper builds its seeded extractors, and through them its two-source extractors and Ramsey graphs, on it.

theorem_7_6: Li's explicit one-bit two-source extractor, with any constant error, for two independent n-bit sources of min-entropy at least c log n, from which the paper reads off Corollary 7.7's Ramsey graphs.

---

X. Li, Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. arXiv:2303.06802 (v1 13 March 2023; v2 30 May 2023, "Fixed some minor errors"); conference version in the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), 1271--1281, DOI 10.1109/FOCS57990.2023.00075 (Crossref record read).

The copy read for this card is arXiv:2303.06802v2 [cs.CC] 30 May 2023, 47 pages, with a text layer; paper p. $n$ $=$ PDF p. $n+2$. The FOCS text has not been compared, and the locators below are the paper's own page numbers. The title page and paper pp. 1--12 and 18--38 were read on rendered page images. The arXiv record names arXiv's non-exclusive distribution license (arXiv:2303.06802), every other right reserved.

Read status: claims checked for Theorems 1.6--1.16 and Corollary 1.9 (pp. 6--7), Theorems 3.11, 6.2 and 6.3 (pp. 21, 30, 31), and Theorems 7.2, 7.4--7.6, 7.11--7.13, 7.18, 7.19, 7.24 and 7.26--7.28, Corollaries 7.7, 7.14, 7.15 and 7.17 and Lemmas 7.3, 7.16, 7.23 and 7.25 (pp. 33--38), with the definitions they use, read clause by clause on the page images; the survey (pp. 1--5) and the first part of the overview of the techniques (Section 1.2, pp. 7--12) were read for the account below. The proofs of Theorems 3.11 and 6.2, the construction behind Lemma 5.1 (pp. 27--28) and the sketch for Theorem 6.3 were read for the result pages' pointers and not checked; no other proof was read.

Li supplies what the paper calls the last missing link in a long chain of reductions in extractor theory, which had reduced the applications below to explicit two-source and affine non-malleable extractors at some constant entropy rate below $1$ with error $2^{-\Omega(n)}$ (p. 8). Theorem 6.2 (p. 30) gives the two-source one, for two sources of min-entropy $(1-\gamma)n$ with $\gamma$ a fixed constant, and Theorem 1.12 (restated as Theorem 3.11, p. 21) the affine one, for entropy $(1-\gamma)n$, both with error $2^{-\Omega(n)}$. Theorem 1.11 (restated as Theorem 6.3, p. 31, with a proof sketch) lowers the two-source requirement to a first source of entropy $(2/3+\gamma)n$, for any constant $\gamma\in(0,1)$, and a second of min-entropy $k\ge C\log n$, with error $2^{-\Omega(k)}$; the paper says it is not necessary for its applications. These yield an asymptotically optimal strong seeded non-malleable extractor (Theorem 1.10), extractors for interleaved, sumset, affine and small-space sources at entropy $c\log n$ or $2s+c\log n$ (Theorems 1.6--1.8), optimal two-round privacy amplification against an active adversary (Theorem 1.13), constant-rate non-malleable codes against 2-split-state and affine tampering with error $2^{-\Omega(k)}$ (Theorems 1.14, 1.15), and a function requiring strongly read-once linear branching programs of size $2^{n-O(\log n)}$ (Theorem 1.16). The method starts from the Chattopadhyay--Zuckerman additive-combinatorial non-malleable extractor (the paper's [24], 2014) and extracts independence from a single weak source under an arbitrary tampering function, producing constantly many rows, one of which keeps high entropy given its tampered counterpart; the alternating extraction that finishes the construction then needs only the constant-length row index as advice, whereas advice of length at least $\log(1/\epsilon)$ had capped the error of earlier constructions (pp. 8--11). For the Erdős problem on explicitly constructing Ramsey graphs, Corollary 1.9 (restated as Corollary 7.7) gives, for a constant $c>1$ and every integer $N$, a strongly explicit graph on $N$ vertices with no clique or independent set of size $\log^cN$, derived by "a standard argument" from the two-source extractor for min-entropy $c\log n$ with constant error (Theorem 7.6). The paper makes no priority claim at either statement, but its survey (pp. 1--2) names as the previous best two-source extractor in entropy that of its reference [81] (Li, CCC 2019), whose Ramsey graph has no clique or independent set of size $(\log N)^{O(\log\log\log N/\log\log\log\log N)}$, short of a polylogarithmic bound. The library has no card for [81] or for the Chattopadhyay--Zuckerman papers [24] and [26], and the site credits the $(\log n)^C$ bound to this paper.

Contents

• Corollary 1.9 (p. 6): a constant $c>1$ and, for every $N$, a (strongly) explicit graph on $N$ vertices with no clique or independent set of size $K=\log^cN$; restated as Corollary 7.7 (p. 35) after Theorem 7.6.
• Theorem 1.6 (p. 6): for every constant $\epsilon>0$ some $c>1$ and an explicit one-bit extractor of error $\epsilon$ for every interleaving of two independent $(n,k)$ sources with $k\ge c\log n$; restated as Corollary 7.15 (p. 36).
• Theorem 1.7 (p. 6): explicit one-bit extractors of constant error for the sum of two independent $(n,k)$ sources and for affine sources, at $k\ge c\log n$; Theorem 7.13 and Corollary 7.14 (p. 36).
• Theorem 1.8 (p. 6): the same for space-$s$ sources of min-entropy $k\ge2s+c\log n$; Corollary 7.17 (p. 36).
• Theorem 1.10 (p. 6): for every constant $\gamma>0$, with a constant $C>0$, an explicit strong seeded non-malleable extractor whose seed has length $d=C\log(n/\epsilon)$, for $(n,k)$ sources with $k\ge C\log(d/\epsilon)$, with error $\epsilon\in(0,1)$ and output length $(1-\gamma)k/2$; Theorem 7.18 (p. 36), the case $t=1$ of Theorem 7.4 (p. 34).
• Theorem 1.11 (p. 6): an explicit $((2/3+\gamma)n,k,2^{-\Omega(k)})$ two-source non-malleable extractor with $k\ge C\log n$ and output length $\Omega(k)$; Theorem 6.3 (p. 31).
• Theorem 1.12 (p. 6): an explicit $((1-\gamma)n,2^{-\Omega(n)})$ affine non-malleable extractor with output length $\Omega(n)$; Theorem 3.11 (p. 21).
• Theorem 1.13 (p. 7): two-round privacy amplification against an active adversary with security parameter $s\le\alpha k$, entropy loss $O(\log\log n+s)$ and communication $O(\log n+s)$; Theorem 7.19 (p. 36).
• Theorem 1.14 (p. 7): a non-malleable code against 2-split-state tampering with rate $\Omega(1)$ and error $2^{-\Omega(k)}$; Theorem 7.24 (p. 37).
• Theorem 1.15 (p. 7): the same against affine tampering; Theorem 7.26 (p. 37).
• Theorem 1.16 (p. 7): an explicit function requiring strongly read-once linear branching programs of size $2^{n-O(\log n)}$; Theorem 7.28 (p. 38).
• Theorem 6.2 (p. 30): an explicit $((1-\gamma)n,2^{-\Omega(n)})$ two-source non-malleable extractor with output length $\Omega(n)$, the input to Theorem 7.4.
• Theorem 7.6 (p. 35): for every constant $\epsilon>0$ some $c>1$ and an explicit one-bit two-source extractor of error $\epsilon$ for min-entropy $k\ge c\log n$, from Theorems 7.4 and 7.5.

Compiled scope

The title page and paper pp. 1--12 and 18--38 were read on the page images; the constructions and proofs were read only as the Read status says. Nothing here is independently reviewed.

Source: https://arxiv.org/abs/2303.06802.

Bears on. #78: Corollary 1.9 gives explicit graphs on $N$ vertices with no clique or independent set of size $\log^cN$ for an unspecified constant $c>1$; inverted, that is the constructive bound $R(k)>2^{k^{1/c}}$, subexponential in $k$, so it does not give the problem's $R(k)>C^k$. The paper derives it from Theorem 1.6 in the introduction and from Theorem 7.6 in the body, which rests on Theorem 6.2 through Theorem 7.4.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.