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

Silas Richelson; Sourya Roy

doi:10.48550/arxiv.2201.11166

Back

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

Preprint

Open access

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

Silas Richelson and Sourya Roy

ArXiv.org

Cornell University

01/26/2022

DOI: 10.48550/arxiv.2201.11166

Files and links (1)

url

https://doi.org/10.48550/arXiv.2201.11166View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

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.

Information Theory

Details

Title: Subtitle: Analyzing Ta-Shma's Code via the Expander Mixing Lemma
Creators: Silas Richelson
Sourya Roy
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2201.11166
ISSN: 2331-8422
Publisher: Cornell University
Language: English
Date posted: 01/26/2022
Academic Unit: Computer Science
Record Identifier: 9984446730702771

Metrics

31 Record Views