NUK - logo
E-resources
Full text
Peer reviewed Open access
  • Analyzing Ta-Shma's Code vi...
    Richelson, Silas; Roy, Sourya

    IEEE transactions on information theory, 02/2024, Volume: 70, Issue: 2
    Journal Article

    Random walks in expander graphs and their various derandomizations ( e.g ., replacement=zig-zag 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 .