Codes with the multiplication property
summary
Constructs LDPC codes on a triangle complex built from coset-style groups over F_p[t]/(irreducible of degree n), embedding each triangle as a point in F_p^{9n} so that the triangles touching any edge lie on an affine line (p triangles per edge), links have about p^3 edges and 2p^2 vertices, and the global code enforces Reed‑Solomon constraints on those lines. Claims: distance is good once line degree d exceeds ~sqrt(p), local testability for d < p/4 holds by a Spielman‑type argument, and the code is multiplication codes whenever d1+d2 < p; rate lower bounds give only a sublinear (constant‑power) dimension, not linear.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation
- 0:55Multiplication codes and PCs
- 8:17Expander codes
- 13:42An open research question
- 15:32High-dimensional codes
- 19:11Geometric construction
- 40:36Summary of code properties
- 44:19Discussion and Q&A
related talks
01h 09mWhen Cryptography Meets Modern Channel Coding
41mHigh-Rate Fair-Density Parity-Check Codes
34mHigh-entropy dual functions and locally decodable codes
58mBosonic (And Other) Codes With Interesting Logical Gate Sets
01h 02mTree PCPs
04mError-Correcting Codes: Theory and Practice
53mFourier Growth of XOR-Fibers of Communication Protocols
24mOn the download rate of homomorphic secret sharing