Subspace Evasive Sets

Details Subspace Evasive Sets Subspace Evasive Sets

2011-10-26

arxiv.org/abs/1110.5696v1

Computer Science

Computational Complexity

16 pages

Scientific paper

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) who showed how such constructions over the binary field can be used to construct explicit Ramsey graphs. More recently, Guruswami (2011) showed that, over large finite fields (of size polynomial in n), subspace evasive sets can be used to obtain explicit list-decodable codes with optimal rate and constant list-size. In this work we construct subspace evasive sets over large fields and use them to reduce the list size of folded Reed-Solomon codes form poly(n) to a constant.

Affiliated with

Also associated with

No associations

Rating

Subspace Evasive Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subspace Evasive Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subspace Evasive Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-716864