English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We introduce a novel family of expander-based error correcting codes. Thesecodes can be sampled with randomness linear in the block-length, and achievelist-decoding capacity (among other local properties). Our expander-based codescan be made starting from any family of sufficiently low-bias codes, and as aconsequence, we give the first construction of a family of algebraic codes thatcan be sampled with linear randomness and achieve list-decoding capacity. Weachieve this by introducing the notion of a pseudorandom puncturing of a code,where we select $n$ indices of a base code $C\subset \mathbb{F}_q^m$ via anexpander random walk on a graph on $[m]$. Concretely, whereas a random linearcode (i.e. a truly random puncturing of the Hadamard code) requires $O(n^2)$random bits to sample, we sample a pseudorandom linear code with $O(n)$ randombits. We show that pseudorandom puncturings satisfy several desirableproperties exhibited by truly random puncturings. In particular, we extend aresult of (Guruswami Mosheiff FOCS 2022) and show that a pseudorandompuncturing of a small-bias code satisfies the same local properties as a randomlinear code with high probability. As a further application of our techniques,we also show that pseudorandom puncturings of Reed Solomon codes arelist-recoverable beyond the Johnson bound, extending a result of (LundPotukuchi RANDOM 2020). We do this by instead analyzing properties of codeswith large distance, and show that pseudorandom puncturings still work well inthis regime.

Pseudorandom Linear Codes are List Decodable to Capacity