Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-004 | 3rd January 2022 19:40

Analyzing Ta-Shma’s Code via the Expander Mixing Lemma



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.

ISSN 1433-8092 | Imprint