### Abstract

We construct explicit subspace-evasive sets. These are subsets of double-struck F ^{n} of size |double-struck 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.

Original language | English (US) |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 351-358 |

Number of pages | 8 |

DOIs | |

State | Published - Jun 26 2012 |

Event | 44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States Duration: May 19 2012 → May 22 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 44th Annual ACM Symposium on Theory of Computing, STOC '12 |
---|---|

Country | United States |

City | New York, NY |

Period | 5/19/12 → 5/22/12 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- affine varieties
- list decodable codes
- pseudo-randomness

## Fingerprint Dive into the research topics of 'Subspace evasive sets'. Together they form a unique fingerprint.

## Cite this

Dvir, Z., & Lovett, S. (2012). Subspace evasive sets. In

*STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing*(pp. 351-358). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214010