Document Open Access Logo

Subspace Designs Based on Algebraic Function Fields

Authors Venkatesan Guruswami, Chaoping Xing, Chen Yuan



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.86.pdf
  • Filesize: 0.51 MB
  • 10 pages

Document Identifiers

Author Details

Venkatesan Guruswami
Chaoping Xing
Chen Yuan

Cite AsGet BibTex

Venkatesan Guruswami, Chaoping Xing, and Chen Yuan. Subspace Designs Based on Algebraic Function Fields. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 86:1-86:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.86

Abstract

Subspace designs are a (large) collection of high-dimensional subspaces {H_i} of F_q^m such that for any low-dimensional subspace W, only a small number of subspaces from the collection have non-trivial intersection with W; more precisely, the sum of dimensions of W cap H_i is at most some parameter L. The notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to algebraic function fields, and instantiating the approach with cyclotomic function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F^n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log(log(n)))).
Keywords
  • Subspace Design
  • Dimension Expander
  • List Decoding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jean Bourgain and Amir Yehudayoff. Expansion in SL₂(ℝ) and monotone expanders. Geometric and Functional Analysis, 23(1):1-41, 2013. URL: http://dx.doi.org/10.1007/s00039-012-0200-9.
  2. Zeev Dvir and Amir Shpilka. Towards dimension expanders over finite fields. Combinatorica, 31(3):305-320, 2011. URL: http://dx.doi.org/10.1007/s00493-011-2540-8.
  3. Zeev Dvir and Avi Wigderson. Monotone expanders: Constructions and applications. Theory of Computing, 6(12):291-308, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a012.
  4. Michael A. Forbes and Venkatesan Guruswami. Dimension expanders via rank condensers. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 800-814, 2015. Extended full version available as ECCC Technical Report TR14-162. Google Scholar
  5. Venkatesan Guruswami. Cyclotomic function fields, Artin-Frobenius automorphisms, and list error-correction with optimal rate. Algebra and Number Theory, 4(4):433-463, 2010. Preliminary version in STOC 2009. Google Scholar
  6. Venkatesan Guruswami. Linear-algebraic list decoding of folded Reed-Solomon codes. In Proceedings of the 26th IEEE Conference on Computational Complexity, June 2011. Google Scholar
  7. Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161-185, 2016. Preliminary version in FOCS 2013. URL: http://dx.doi.org/10.1007/s00493-014-3169-1.
  8. Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of Reed-Solomon codes. IEEE Transactions on Information Theory, 59(6):3257-3268, 2013. URL: http://dx.doi.org/10.1109/TIT.2013.2246813.
  9. Venkatesan Guruswami, Carol Wang, and Chaoping Xing. Explicit list-decodable rank-metric and subspace codes via subspace designs. IEEE Trans. Information Theory, 62(5):2707-2718, 2016. Preliminary versions in STOC 2013 and RANDOM 2014. URL: http://dx.doi.org/10.1109/TIT.2016.2544347.
  10. Venkatesan Guruswami and Chaoping Xing. Folded codes from function fields and improved optimal rate list decoding. In Proceedings of the 44th ACM Symposium on Theory of Computing, pages 339-350, 2012. Google Scholar
  11. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 843-852, June 2013. Extended version available as ECCC Technical Report TR12-146. Google Scholar
  12. Venkatesan Guruswami and Chaoping Xing. Optimal rate algebraic list decoding using narrow ray class fields. J. Comb. Theory, Ser. A, 129:160-183, 2015. Preliminary version in SODA 2014 under slightly different title. Google Scholar
  13. David R. Hayes. Explicit class field theory for rational function fields. Trans. Amer. Math. Soc., 189:77-91, March 1974. Google Scholar
  14. Liming Ma, Chaoping Xing, and Sze Ling Yeo. On automorphism groups of cyclotomic function fields over finite fields. Journal of Number Theory, 169:406-419, 2016. URL: http://dx.doi.org/10.1016/j.jnt.2016.05.026.
  15. Henning Stichtenoth. Algebraic function fields and codes. GMT 254, Springer-Verlag, Berlin, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail