摘要 : We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have applications to constructing efficiently list-decodable codes, as... 展开 We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have applications to constructing efficiently list-decodable codes, as well as in compressed sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate 1-epsilon for any epsilon > 0. We can plug our high-rate codes into a construction of Alon and Luby (1996), recently highlighted by Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates R, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code.A slight strengthening of our result would imply linear-time and optimally list-decodable codes for all rates. Thus, our result is a step in the direction of solving this important problem. (C) 2018 Elsevier Inc. All rights reserved. 收起