Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding

Previous Article
Weight distributions of a class of cyclic codes from $\Bbb F_l$-conjugates
AMC Home
This Issue
Next Article
On weighted minihypers in finite projective spaces of square order

August 2015, 9(3): 311-339. doi: 10.3934/amc.2015.9.311

Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding

Henry Cohn ^1, and Nadia Heninger ^2,

1.	Microsoft Research New England, One Memorial Drive, Cambridge, MA 02142, United States
2.	Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, United States

Received February 2014 Published July 2015

Abstract
Related Papers

We develop a framework for solving polynomial equations with size constraints on solutions. We obtain our results by showing how to apply a technique of Coppersmith for finding small solutions of polynomial equations modulo integers to analogous problems over polynomial rings, number fields, and function fields. This gives us a unified view of several problems arising naturally in cryptography, coding theory, and the study of lattices. We give (1) a polynomial-time algorithm for finding small solutions of polynomial equations modulo ideals over algebraic number fields, (2) a faster variant of the Guruswami-Sudan algorithm for list decoding of Reed-Solomon codes, and (3) an algorithm for list decoding of algebraic-geometric codes that handles both single-point and multi-point codes. Coppersmith's algorithm uses lattice basis reduction to find a short vector in a carefully constructed lattice; powerful analogies from algebraic number theory allow us to identify the appropriate analogue of a lattice in each application and provide efficient algorithms to find a suitably short vector, thus allowing us to give completely parallel proofs of the above theorems.

Keywords: Coppersmith's theorem, Lattice basis reduction, list decoding..

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

References:

[1]	M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reductions, in Proc. 30th Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 1998, 10-19. doi: 10.1145/276698.276705.
[2]	M. Ajtai, R. Kumar and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in Proc. 33rd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2001, 601-610. doi: 10.1145/380752.380857.
[3]	M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265. doi: 10.1109/TIT.2005.850097.
[4]	P. Beelen and K. Brander, Efficient list decoding of a class of algebraic-geometry codes, Adv. Math. Commun., 4 (2010), 485-518. doi: 10.3934/amc.2010.4.485.
[5]	P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comput., 45 (2010), 773-786. doi: 10.1016/j.jsc.2010.03.010.
[6]	D. J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge Univ. Press, Cambridge, 2008, 421-446.
[7]	D. J. Bernstein, List decoding for binary Goppa codes, in Coding and Cryptology, Springer-Verlag, Berlin, 2011, 62-80. doi: 10.1007/978-3-642-20901-7_4.
[8]	J.-F. Biasse and G. Quintin, An algorithm for list decoding number field codes, in 2012 IEEE Int. Symp. Inf. Theory Proc., IEEE, 2012, 91-95. doi: 10.1109/ISIT.2012.6284696.
[9]	D. Bleichenbacher and P. Q. Nguyen, Noisy polynomial interpolation and noisy Chinese remaindering, in Adv. Crypt. - EUROCRYPT 2000, Springer-Verlag, Berlin, 2000, 53-69. doi: 10.1007/3-540-45539-6_4.
[10]	J. Blömer and A. May, New partial key exposure attacks on RSA, in Adv. Crypt. - CRYPTO 2003, Springer-Verlag, Berlin, 2003, 27-43. doi: 10.1007/978-3-540-45146-4_2.
[11]	D. Boneh, Finding smooth integers in short intervals using CRT decoding, in Proc. 32nd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2000, 265-272. doi: 10.1145/335305.335337.
[12]	D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, in Adv. Crypt. - ASIACRYPT '98, Springer-Verlag, Berlin, 1998, 25-34. doi: 10.1007/3-540-49649-1_3.
[13]	J. Buchmann, T. Takagi and U. Vollmer, Number field cryptography, in High Primes and Misdemeanours, Amer. Math. Soc., Providence, 2004, 111-121.
[14]	M. F. I. Chowdhury, C.-P. Jeannerod, V. Neiger, É. Schost and G. Villard, Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approxima-tions, IEEE Trans. Inf. Theory, 61 (2015), 2370-2387. doi: 10.1109/TIT.2015.2416068.
[15]	H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02945-9.
[16]	H. Cohn and N. Heninger, Approximate common divisors via lattices, in Proc. 10th Algor. Number Theory Symp., Math. Sci. Publ., Berkeley, 2013, 271-293. doi: 10.2140/obs.2013.1.271.
[17]	D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030.
[18]	D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 20-31. doi: 10.1007/3-540-44670-2_3.
[19]	D. Coppersmith, N. Howgrave-Graham and S. V. Nagaraj, Divisors in residue classes, constructively, Math. Comp., 77 (2008), 531-545. doi: 10.1090/S0025-5718-07-02007-8.
[20]	N. Coxon, List decoding of number field codes, Des. Codes Cryptogr., 72 (2014), 687-711. doi: 10.1007/s10623-013-9803-x.
[21]	C. Fieker and M. E. Pohst, On lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 1996, 133-139. doi: 10.1007/3-540-61581-4_48.
[22]	C. Fieker and D. Stehlé, Short bases of lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 2010, 157-173. doi: 10.1007/978-3-642-14518-6_15.
[23]	J. von zur Gathen, Hensel and Newton methods in valuation rings, Math. Comp., 42 (1984), 637-661. doi: 10.2307/2007608.
[24]	J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 2nd edition, Cambridge Univ. Press, Cambridge, 2003.
[25]	J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp., 45 (1985), 251-261. doi: 10.2307/2008063.
[26]	P. Giorgi, C.-P. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. 2003 Int. Symp. Symb. Algebr. Comput., Assoc. Comput. Mach., New York, 2003, 135-142. doi: 10.1145/860854.860889.
[27]	E. Grigorescu and C. Peikert, List decoding Barnes-Wall lattices, in Proc. 27th IEEE Conf. Comput. Compl., IEEE Comp. Soc., Los Alamitos, 2012, 316-325. doi: 10.1109/CCC.2012.33.
[28]	V. Guruswami and A. Rudra, Explicit codes achieving list decoding capacity: error correction with optimal redundancy, IEEE Trans. Inf. Theory, 54 (2008), 135-150. doi: 10.1109/TIT.2007.911222.
[29]	V. Guruswami, A. Sahai and M. Sudan, "Soft-decision'' decoding of Chinese remainder codes, in Proc. 41st Ann. Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2000, 159-168. doi: 10.1109/SFCS.2000.892076.
[30]	V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767. doi: 10.1109/18.782097.
[31]	N. Howgrave-Graham, Approximate integer common divisors, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 51-66. doi: 10.1007/3-540-44670-2_6.
[32]	M.-D. Huang and D. Ierardi, Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve, J. Symb. Comput., 18 (1994), 519-539. doi: 10.1006/jsco.1994.1063.
[33]	T. Kailath, Linear Systems, Prentice-Hall, Inc., Upper Saddle River, 1980.
[34]	S. V. Konyagin and T. Steger, On polynomial congruences, Math. Notes, 55 (1994), 596-600. doi: 10.1007/BF02110354.
[35]	A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer Algebra, Springer-Verlag, Berlin, 1983, 245-254. doi: 10.1007/3-540-12868-9_108.
[36]	A. K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987), 591-598. doi: 10.1137/0216040.
[37]	H. W. Lenstra, Algorithms in algebraic number theory, Bull. Amer. Math. Soc., 26 (1992), 211-244. doi: 10.1090/S0273-0979-1992-00284-7.
[38]	A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454.
[39]	D. Lorenzini, An Invitation to Arithmetic Geometry, Amer. Math. Soc., Providence, 1996. doi: 10.1090/gsm/009.
[40]	V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in Adv. Crypt. - EUROCRYPT 2010, Springer-Verlag, Berlin, 2010, 1-23. doi: 10.1007/978-3-642-13190-5_1.
[41]	K. Manders and L. Adleman, NP-complete decision problems for quadratic polynomials, in Proc. 8th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1976, 23-29. doi: 10.1145/800113.803627.
[42]	R. C. Mason, Diophantine Equations over Function Fields, Cambridge Univ. Press, Cambridge, 1984. doi: 10.1017/CBO9780511752490.
[43]	A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, Univ. Paderborn, 2003.
[44]	A. May, Using LLL-reduction for solving RSA and factorization problems, in The LLL Algorithm, Springer-Verlag, Berlin, 2010, 315-348. doi: 10.1007/978-3-642-02295-1_10.
[45]	M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation, in Proc. 31st Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1999, 245-254. doi: 10.1145/301250.301312.
[46]	F. Parvaresh and A. Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time, in Proc. 46th IEEE Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2005, 285-294. doi: 10.1109/SFCS.2005.29.
[47]	C. Peikert and A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in Proc. 39th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2007, 478-487. doi: 10.1145/1250790.1250860.
[48]	M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002. doi: 10.1007/978-1-4757-6046-0.
[49]	M. A. Shokrollahi and H. Wasserman, List decoding of algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 432-437. doi: 10.1109/18.748993.
[50]	V. Shoup, OAEP reconsidered, in Adv. Crypt. - CRYPTO 2001, Springer-Verlag, Berlin, 2001, 239-259. doi: 10.1007/3-540-44647-8_15.
[51]	H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-540-76878-4.
[52]	M. Sudan, Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, Berlin, 2001, 36-45. doi: 10.1007/3-540-45624-4_4.
[53]	V. Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, in Proc. 44th ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2012, 887-898. doi: 10.1145/2213977.2214056.

show all references

References:

[1]	M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reductions, in Proc. 30th Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 1998, 10-19. doi: 10.1145/276698.276705.
[2]	M. Ajtai, R. Kumar and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in Proc. 33rd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2001, 601-610. doi: 10.1145/380752.380857.
[3]	M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265. doi: 10.1109/TIT.2005.850097.
[4]	P. Beelen and K. Brander, Efficient list decoding of a class of algebraic-geometry codes, Adv. Math. Commun., 4 (2010), 485-518. doi: 10.3934/amc.2010.4.485.
[5]	P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comput., 45 (2010), 773-786. doi: 10.1016/j.jsc.2010.03.010.
[6]	D. J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge Univ. Press, Cambridge, 2008, 421-446.
[7]	D. J. Bernstein, List decoding for binary Goppa codes, in Coding and Cryptology, Springer-Verlag, Berlin, 2011, 62-80. doi: 10.1007/978-3-642-20901-7_4.
[8]	J.-F. Biasse and G. Quintin, An algorithm for list decoding number field codes, in 2012 IEEE Int. Symp. Inf. Theory Proc., IEEE, 2012, 91-95. doi: 10.1109/ISIT.2012.6284696.
[9]	D. Bleichenbacher and P. Q. Nguyen, Noisy polynomial interpolation and noisy Chinese remaindering, in Adv. Crypt. - EUROCRYPT 2000, Springer-Verlag, Berlin, 2000, 53-69. doi: 10.1007/3-540-45539-6_4.
[10]	J. Blömer and A. May, New partial key exposure attacks on RSA, in Adv. Crypt. - CRYPTO 2003, Springer-Verlag, Berlin, 2003, 27-43. doi: 10.1007/978-3-540-45146-4_2.
[11]	D. Boneh, Finding smooth integers in short intervals using CRT decoding, in Proc. 32nd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2000, 265-272. doi: 10.1145/335305.335337.
[12]	D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, in Adv. Crypt. - ASIACRYPT '98, Springer-Verlag, Berlin, 1998, 25-34. doi: 10.1007/3-540-49649-1_3.
[13]	J. Buchmann, T. Takagi and U. Vollmer, Number field cryptography, in High Primes and Misdemeanours, Amer. Math. Soc., Providence, 2004, 111-121.
[14]	M. F. I. Chowdhury, C.-P. Jeannerod, V. Neiger, É. Schost and G. Villard, Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approxima-tions, IEEE Trans. Inf. Theory, 61 (2015), 2370-2387. doi: 10.1109/TIT.2015.2416068.
[15]	H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02945-9.
[16]	H. Cohn and N. Heninger, Approximate common divisors via lattices, in Proc. 10th Algor. Number Theory Symp., Math. Sci. Publ., Berkeley, 2013, 271-293. doi: 10.2140/obs.2013.1.271.
[17]	D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030.
[18]	D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 20-31. doi: 10.1007/3-540-44670-2_3.
[19]	D. Coppersmith, N. Howgrave-Graham and S. V. Nagaraj, Divisors in residue classes, constructively, Math. Comp., 77 (2008), 531-545. doi: 10.1090/S0025-5718-07-02007-8.
[20]	N. Coxon, List decoding of number field codes, Des. Codes Cryptogr., 72 (2014), 687-711. doi: 10.1007/s10623-013-9803-x.
[21]	C. Fieker and M. E. Pohst, On lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 1996, 133-139. doi: 10.1007/3-540-61581-4_48.
[22]	C. Fieker and D. Stehlé, Short bases of lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 2010, 157-173. doi: 10.1007/978-3-642-14518-6_15.
[23]	J. von zur Gathen, Hensel and Newton methods in valuation rings, Math. Comp., 42 (1984), 637-661. doi: 10.2307/2007608.
[24]	J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 2nd edition, Cambridge Univ. Press, Cambridge, 2003.
[25]	J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp., 45 (1985), 251-261. doi: 10.2307/2008063.
[26]	P. Giorgi, C.-P. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. 2003 Int. Symp. Symb. Algebr. Comput., Assoc. Comput. Mach., New York, 2003, 135-142. doi: 10.1145/860854.860889.
[27]	E. Grigorescu and C. Peikert, List decoding Barnes-Wall lattices, in Proc. 27th IEEE Conf. Comput. Compl., IEEE Comp. Soc., Los Alamitos, 2012, 316-325. doi: 10.1109/CCC.2012.33.
[28]	V. Guruswami and A. Rudra, Explicit codes achieving list decoding capacity: error correction with optimal redundancy, IEEE Trans. Inf. Theory, 54 (2008), 135-150. doi: 10.1109/TIT.2007.911222.
[29]	V. Guruswami, A. Sahai and M. Sudan, "Soft-decision'' decoding of Chinese remainder codes, in Proc. 41st Ann. Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2000, 159-168. doi: 10.1109/SFCS.2000.892076.
[30]	V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767. doi: 10.1109/18.782097.
[31]	N. Howgrave-Graham, Approximate integer common divisors, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 51-66. doi: 10.1007/3-540-44670-2_6.
[32]	M.-D. Huang and D. Ierardi, Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve, J. Symb. Comput., 18 (1994), 519-539. doi: 10.1006/jsco.1994.1063.
[33]	T. Kailath, Linear Systems, Prentice-Hall, Inc., Upper Saddle River, 1980.
[34]	S. V. Konyagin and T. Steger, On polynomial congruences, Math. Notes, 55 (1994), 596-600. doi: 10.1007/BF02110354.
[35]	A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer Algebra, Springer-Verlag, Berlin, 1983, 245-254. doi: 10.1007/3-540-12868-9_108.
[36]	A. K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987), 591-598. doi: 10.1137/0216040.
[37]	H. W. Lenstra, Algorithms in algebraic number theory, Bull. Amer. Math. Soc., 26 (1992), 211-244. doi: 10.1090/S0273-0979-1992-00284-7.
[38]	A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454.
[39]	D. Lorenzini, An Invitation to Arithmetic Geometry, Amer. Math. Soc., Providence, 1996. doi: 10.1090/gsm/009.
[40]	V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in Adv. Crypt. - EUROCRYPT 2010, Springer-Verlag, Berlin, 2010, 1-23. doi: 10.1007/978-3-642-13190-5_1.
[41]	K. Manders and L. Adleman, NP-complete decision problems for quadratic polynomials, in Proc. 8th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1976, 23-29. doi: 10.1145/800113.803627.
[42]	R. C. Mason, Diophantine Equations over Function Fields, Cambridge Univ. Press, Cambridge, 1984. doi: 10.1017/CBO9780511752490.
[43]	A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, Univ. Paderborn, 2003.
[44]	A. May, Using LLL-reduction for solving RSA and factorization problems, in The LLL Algorithm, Springer-Verlag, Berlin, 2010, 315-348. doi: 10.1007/978-3-642-02295-1_10.
[45]	M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation, in Proc. 31st Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1999, 245-254. doi: 10.1145/301250.301312.
[46]	F. Parvaresh and A. Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time, in Proc. 46th IEEE Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2005, 285-294. doi: 10.1109/SFCS.2005.29.
[47]	C. Peikert and A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in Proc. 39th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2007, 478-487. doi: 10.1145/1250790.1250860.
[48]	M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002. doi: 10.1007/978-1-4757-6046-0.
[49]	M. A. Shokrollahi and H. Wasserman, List decoding of algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 432-437. doi: 10.1109/18.748993.
[50]	V. Shoup, OAEP reconsidered, in Adv. Crypt. - CRYPTO 2001, Springer-Verlag, Berlin, 2001, 239-259. doi: 10.1007/3-540-44647-8_15.
[51]	H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-540-76878-4.
[52]	M. Sudan, Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, Berlin, 2001, 36-45. doi: 10.1007/3-540-45624-4_4.
[53]	V. Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, in Proc. 44th ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2012, 887-898. doi: 10.1145/2213977.2214056.

[1]	Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002
[2]	Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[3]	Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011
[4]	Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009
[5]	Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331
[6]	Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[7]	John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete and Continuous Dynamical Systems, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367
[8]	Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics and Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011
[9]	Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete and Continuous Dynamical Systems - S, 2015, 8 (2) : 313-321. doi: 10.3934/dcdss.2015.8.313
[10]	Sergei Ivanov. On Helly's theorem in geodesic spaces. Electronic Research Announcements, 2014, 21: 109-112. doi: 10.3934/era.2014.21.109
[11]	Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015
[12]	Daniele Mundici. The Haar theorem for lattice-ordered abelian groups with order-unit. Discrete and Continuous Dynamical Systems, 2008, 21 (2) : 537-549. doi: 10.3934/dcds.2008.21.537
[13]	Nikolai Dokuchaev. Dimension reduction and Mutual Fund Theorem in maximin setting for bond market. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1039-1053. doi: 10.3934/dcdsb.2011.16.1039
[14]	C. D. Ahlbrandt, A. C. Peterson. A general reduction of order theorem for discrete linear symplectic systems. Conference Publications, 1998, 1998 (Special) : 7-18. doi: 10.3934/proc.1998.1998.7
[15]	Anne-Sophie de Suzzoni. Consequences of the choice of a particular basis of $L^2(S^3)$ for the cubic wave equation on the sphere and the Euclidean space. Communications on Pure and Applied Analysis, 2014, 13 (3) : 991-1015. doi: 10.3934/cpaa.2014.13.991
[16]	Quyen Tran, Harbir Antil, Hugo Díaz. Optimal control of parameterized stationary Maxwell's system: Reduced basis, convergence analysis, and a posteriori error estimates. Mathematical Control and Related Fields, 2022 doi: 10.3934/mcrf.2022003
[17]	Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete and Continuous Dynamical Systems, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067
[18]	V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413
[19]	Jacques Féjoz. On "Arnold's theorem" on the stability of the solar system. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3555-3565. doi: 10.3934/dcds.2013.33.3555
[20]	Lena Noethen, Sebastian Walcher. Tikhonov's theorem and quasi-steady state. Discrete and Continuous Dynamical Systems - B, 2011, 16 (3) : 945-961. doi: 10.3934/dcdsb.2011.16.945

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Henry Cohn Nadia Heninger
on Google Scholar
Henry Cohn Nadia Heninger

[Back to Top]