Constructing Small-Bias Sets from Algebraic-Geometric Codes

by Avraham Ben-Aroya and Amnon Ta-Shma

Theory of Computing, Volume 9(5), pp. 253-272, 2013

Bibliography with links to cited articles

[1]   Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inform. Theory, 38(2):509–516, 1992. Preliminary version in ISIT’91. [doi:10.1109/18.119713]

[2]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992. Preliminary version in FOCS’90. [doi:10.1002/rsa.3240030308]

[3]   Avraham Ben-Aroya and Amnon Ta-Shma: Constructing small-bias sets from algebraic-geometric codes. In Proc. 50th FOCS, pp. 191–197. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.44]

[4]   William Fulton: Algebraic Curves: An Introduction to Algebraic Geometry. Third edition, 2008. Author’s version.

[5]   Arnaldo Garcia and Henning Stichtenoth, editors. Topics in Geometry, Coding Theory and Cryptography. Volume 6. Springer, 2007. Available from Springer.

[6]   Serge Lang: Algebra. Springer, revised third edition, 2002. Available from Springer.

[7]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. Preliminary version in STOC’90. [doi:10.1137/0222053]

[8]   Henning Stichtenoth: Algebraic Function Fields and Codes. Springer, 1993. Available from Springer.

[9]   Henning Stichtenoth: Private communication, 2009.

[10]   Michael A. Tsfasman, Serge G. Vlăduţ, and Thomas Zink: Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Mathematische Nachrichten, 109(1):21–28, 1982. [doi:10.1002/mana.19821090103]

[11]   José Felipe Voloch: Special divisors of large dimension on curves with many points over finite fields. Portugaliae Mathematica, 68(1):103–107, 2011. [doi:10.4171/PM/1882]