论文标题
通过扩展器混合引理分析Ta-Shma的代码
Analyzing Ta-Shma's Code via the Expander Mixing Lemma
论文作者
论文摘要
在扩展器图中随机步行及其各种范围（例如，更换/锯齿形产品）是伪随身界的宝贵工具。最近，Ta-Shma在他突破性的二进制线性代码的突破性构造中使用了S范围的替代步行，几乎与Gilbert-Varshamov Bound相匹配（Stoc 2017）。 Ta-Shma的原始分析完全是线性代数，随后的发展继承了此观点。在这项工作中，我们使用膨胀剂混合引理的重复应用从组合的角度重新播放了Ta-Shma的分析。我们希望这种替代观点能够更好地了解Ta-Shma的构建。作为我们技术的附加应用，我们给出了插座弹置诱饵的替代证明。
Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma's original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma's analysis from a combinatorial point of view using repeated application of the expander mixing lemma. We hope that this alternate perspective will yield a better understanding of Ta-Shma's construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma.
