本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #189
- 日期：2026-03-18
摘要
F_2^n 的子集是 eps 偏置的，這意味著任何一組位的奇偶校驗是偶數或奇數，機率 eps 接近 1/2，是去隨機化的強大工具。簡單的隨機構造表明存在大小為 O(n/eps^2) 的此類集合，並且已知的確定性構造可實現大小為 O(n/eps^3)、O(n^2/eps^2) 和 O((n/eps^2)^{5/4}) 的集合。我們不是完全去隨機化這些集合以換取使其變大，而是嘗試部分去隨機化，同時保持它們較小，用盡可能少的隨機位構建大小為 O(n/eps^2) 的集合。樸素的隨機構造需要 O(n^2/eps^2) 隨機位元。我們給出兩種結構。第一個使用 Nisan 的空間限制偽隨機產生器對糾錯碼的民間傳說機率構造進行部分去隨機化，並且需要 O(n log (1/eps)) 位。我們的第二個構造需要 O(n log (n/eps)) 位，但更基本；它為 Alon、Goldreich、H{\aa}stad 和 Peralta 上的 Legendre 符號構造添加了隨機性，並使用 Weil 和來限制偏差的高矩。