|| The Generalized Covering Radii of Linear Codes
||Dor Elimelech, Ben-Gurion University of the Negev, Israel; Marcelo Firer, University of Campinas, Brazil; Moshe Schwartz, Ben-Gurion University of the Negev, Israel|
||D1-S5-T2: Distance Metrics
||Monday, 12 July, 23:20 - 23:40
||Monday, 12 July, 23:40 - 00:00
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.