All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD1-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.