| Paper ID | D1-S5-T2.2 |
| Paper Title |
The Generalized Covering Radii of Linear Codes |
| Authors |
Dor Elimelech, Ben-Gurion University of the Negev, Israel; Marcelo Firer, University of Campinas, Brazil; Moshe Schwartz, Ben-Gurion University of the Negev, Israel |
| Session |
D1-S5-T2: Distance Metrics |
| Chaired Session: |
Monday, 12 July, 23:20 - 23:40 |
| Engagement Session: |
Monday, 12 July, 23:40 - 00:00 |
| Abstract |
Motivated by an application to database linear querying, such as private information-retrieval protocols, we suggest a fundamental property of linear codes - the generalized covering radius. The generalized covering-radius hierarchy of a linear code characterizes the trade-off between storage amount, latency, and access complexity, in such database systems. Several equivalent definitions are provided, showing this as a combinatorial, geometric, and algebraic notion. We derive bounds on the code parameters in relation with the generalized covering radii, study the effect of simple code operations, and describe a connection with generalized Hamming weights.
|
