Name
Abstract | ||
|---|---|---|
We construct explicit subspace-evasive sets. These are subsets of Fn of size |F|(1-ε)n whose intersection with any k-dimensional subspace is bounded by a constant c(k,ε). This problem was raised by Guruswami (CCC 2011) as it leads to optimal rate list-decodable codes of constant list size. The main technical ingredient is the construction of k low-degree polynomials whose common set of zeros has small intersection with any k-dimensional subspace. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2213977.2214010 | STOC |
Keywords | DocType | Volume |
constant c,main technical ingredient,explicit subspace-evasive set,rate list-decodable code,common set,subspace evasive set,constant list size,k low-degree polynomial,small intersection,k-dimensional subspace,algebraic geometry,reed solomon code,list decoding,finite field,computational complexity | Journal | abs/1110.5696 |
Citations | PageRank | References |
17 | 0.81 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeev Dvir | 1 | 437 | 30.85 |
| Shachar Lovett | 2 | 520 | 55.02 |