Journal Publications

Qi Cheng, Shuhong Gao, J. Maurice Rojas, Daqing Wan, Sparse univariate polynomials with many roots over finite fields, Finite Fields and Their Applications, Volume 46, July 2017, Pages 235–246.

Jingguo Bi, Qi Cheng, and J. Maurice Rojas, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, SIAM J. Comput. 45-4 (2016), pp. 1433-1447.

Jincheng Zhuang, Qi Cheng, and Jiyou Li, On Determining Deep Holes of Generalized Reed-Solomon Codes, IEEE Transactions On Information Theory, VOL. 62, NO. 1, January 2016. Pages 199-207.

Jingguo Bi and Qi Cheng, Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices, Theoretical Computer Science, Volume 560, Part 2, Pages 121--130, 2014.

Qi Cheng, Daqing Wan and Jincheng Zhuang, Traps to the BGJT-Algorithm for Discrete Logarithms, LMS Journal of Computation and Mathematics, 17:218--229 (Special issue for ANTS 2014).

Qi Cheng and Jincheng Zhuang, On certain computations of pisot numbers. Information Processing Letters, 113:271–275, 2013.

Qi Cheng and Daqing Wan, A Deterministic Reduction for the Gap Minimum Distance Problem, IEEE Transactions on Information Theory. Vol. 58 No. 11. Pages: 6935 - 6941

Qi Cheng and Yu-Hsin Li, On the minimum gap between sums of square roots of small integers, Theoretical Computer Science 412 (2011): 5458--5465.

Qi Cheng and Daqing Wan, Complexity of Decoding Positive-Rate Primitive Reed-Solomon Codes, IEEE Transactions on Information Theory. Vol. 56, No. 10. Pages: 5217 -- 5222.

Qi Cheng, Xianmeng Meng, Celi Sun and Jiazhe Chen, Bounding the Sum of Square Roots via Lattice Reduction, Mathematics of Computation, 79 (2010), 1109-1122.

Qi Cheng, Sergey P. Tarasov and Mikhail N. Vyalyi, Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing , Theory of Computing Systems. 46(1): 120--142.

Qi Cheng, Hard problems of Algebraic Geometry codes , IEEE Transactions on Information Theory. 54(1): 402--406.

Qi Cheng, Constructing finite field extensions with large order elements , SIAM journal on Discrete Mathematics, 21(3): 726--730.

Qi Cheng and Daqing Wan, On the List and Bounded Distance Decodability of the Reed-Solomon Codes, SIAM journal on Computing, 37(1): 195--209. Special issue on FOCS 2004.

Qi Cheng, Primality Proving via One Round in ECPP and One Iteration in AKS , Journal of Cryptology, 20(3): 375-387.

Qi Cheng and Ming-Deh Huang, On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem , Algorithmica, 46(1), Page 59--68.

G. Aggarwal, Q. Cheng, M.H. Goldwasser, MY Kao, P.M. de Espanse and RT Schweller, Complexities for generalized models of self-assembly, SIAM journal on Computing, 34(6), Pages 1493--1515.

Qi Cheng, On the Bounded Sum-of-digits Discrete Logarithm Problem in Finite Fields , SIAM Journal on Computing, Vol 34, Number 6, Pages 1432--1442, 2005.

Qi Cheng, On the construction of finite field elements of large order, Finite Fields and Their Applications. Vol 11, Issue 3, Pages 358-366, 2005.

Qi Cheng, On the Ultimate Complexity of Factorials, Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429.

Qi Cheng and Ming-Deh Huang, On counting and generating curves over small finite fields, Journal of Complexity, Volume 20, Issues 2-3, p. 284--296, 2004.

Qi Cheng, Straight Line Programs and Torsion Points on Elliptic Curves , Computational Complexity, 12:3-4, 150--161.

Qi Cheng and Fang Fang, Kolmogorov Random Graphs Only Have Trivial Stable Colorings, Information Processing Letters 81, 2002, 133--136.

Q. Cheng, M. Chrobak and G. Sundaram, Computing Simple Paths among Obstacles, Computational Geometry: Theory and Applications, 16(2000), 223-233.


Conference Publications

Jincheng Zhuang and Qi Cheng, Generating Coset Representatives of $PGL_2(\F_q)$ in $PGL_2(\F_{q^2})$, Proceedings of the 11th International Conference on Information Security and Cryptology (Inscrypt 2015), LNCS 9589, Pages: 167--177, 2016.

Qi Cheng, Shuhong Gao, J. Maurice Rojas, and Daqing Wan, Sparse Univariate Polynomials with Many Roots Over a Finite Field, The Thirteenth Conference on Effective Methods in Algebraic Geometry (MEGA) 2015, University of Trento, Italy.

Qi Cheng, Jincheng Zhuang, and Jiyou Li, On determining deep holes of Generalized Reed- Solomon codes, In Proceedings of The 24th International Symposium on Algorithms and Computation (ISAAC), Hong Kong, China, 2013.

Jingguo Bi, Qi Cheng and J. Maurice Rojas, Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields, Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC), June 26-29, Boston, MA, ACM Press, 2013. The winner of Distinguished Paper Award.

Qi Cheng, Joshua E. Hill and Daqing Wan Counting Value Sets: Algorithm and Complexity, Tenth Algorithmic Number Theory Symposium (ANTS-X), San Diego, CA.

Jingguo Bi and Qi Cheng, Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices, The 9th annual conference on Theory and Applications of Models of Computation (TAMC 2012). LNCS 7287. Pages: 143--155.

Qi Cheng, Shuhong Gao and Daqing Wan, Constructing high order elements through subspace polynomials , Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Pages: 1457-1463.

Qi Cheng and Yu-Hsin Li, Finding the smallest gap between sums of square roots. Proceedings of The 9th Latin American Theoretical Informatics Symposium (LATIN 2010), LNCS 6034, Pages: 446--455.

Qi Cheng and Daqing Wan, A Deterministic Reduction for the Gap Minimum Distance Problem, Proceedings of the 41st ACM Symposium on Theory of Computing (STOC 2009), Page 33--38.

Qi Cheng and Daqing Wan, Complexity of Decoding Positive-Rate Reed-Solomon Codes, Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5125, 2008. Updated version

Qi Cheng, Derandomization of Sparse Cyclotomic Integer Zero Testing, FOCS 2007, Pages 74--80. Journal version appeared in Theory of Computing Systems.

Qi Cheng and Elizabeth Murray, On Deciding Deep Holes of Reed-Solomon Codes, Proceedings of TAMC 2007, LNCS 4484, Page 296--305.

Qi Cheng, On comparing sums of square roots of small integers, Proceedings of MFCS 2006, LNCS 4162, Page 250--255.

Qi Cheng and Ming-Deh Huang, On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem, The Proceeding of the 15th Annual International Symposium on Algorithms and Computation (ISAAC), 342--351, LNCS 3341. 2004. Journal version in Algorithmica.

Qi Cheng and Daqing Wan, On the List and Bounded Distance Decodibility of the Reed-Solomon Codes, the Proceeding of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 335--341, 2004. Journal version in SIAM journal on Computing.

Qi Cheng, On the Bounded Sum-of-digits Discrete Logarithm Problem in Finite Fields, Proceeding of Crypto 2004, 201--212, LNCS 3152. Journal version in SIAM Joural on Computing.

Q. Cheng, A. Goel, and P. Moisset. Optimal self-assembly of counters at temperature two, The proceedings of the first conference on Foundations of nanoscience: self-assembled architectures and devices. April 2004.

Qi Cheng, Constructing finite field extensions with large order elements, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004. Journal version in SIAM Journal on Discrete Mathematics.

Ho-Lin Chen, Qi Cheng, Ashish Goel, Ming-Deh Huang and Pablo Moisset de Espanes, Invadable Self-Assembly: Combining Robustness with Efficiency, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004.

L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, and H. Wasserman. Linear self-assemblies: Equilibria, entropy, and convergence rates. "New progress in difference equations"; Editors: Elaydi, Ladas, and Aulbach; Pub: Taylor and Francis, London. 2003.

Qi Cheng, Primality Proving via One Round in ECPP and One Iteration in AKS, Crypto 2003, Santa Barbara, LNCS 2729. Journal version in Journal of Cryptology.

Qi Cheng, On the Ultimate Complexity of Factorials, The 20th International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 2607, Berlin, Germany, 2003. Journal version appeared in Theoretical Computer Science

Qi Cheng, Some Remarks on the L-conjecture, The 13th Annual International Symposium on Algorithms and Computation (ISAAC), LNCS 2518, Vancouver, Canada, 2002. Journal version appeared in Computational Complexity as "Straight Line Programs and Torsion Points on Elliptic Curves".

Len Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo Moisset de Espanes and Paul Rothemund, Combinatorial optimization problems in self-assembly, 34th Annual ACM Symposium on the Theory of Computing(STOC), 2002.

Qi Cheng and Shigenori Uchiyama, Nonuniform polynomial time algorithm to solve decisional Diffie-Hellman problem in finite fields under conjecture, RSA conference cryptographers' track, 2002, LNCS 2271, Springer. Updated version

Leonard Adleman, Qi Cheng, Ashish Goel and Ming-Deh Huang, Running Time and Program Size for Self-assembled Squares, 33th Annual ACM Symposium on the Theory of Computing(STOC), 2001.

Qi Cheng and Ming-Deh Huang, Factoring Polynomials over Finite Fields and Stable Colorings of Tournaments, Algorithmic Number Theory Symposium(ANTS) IV, Lecture Notes in Computer Science 1838, 2000. Updated version

Qi Cheng and Hong Zhu, MNP: A Class of NP Optimization Problems, Proceeding of Annual International Computing and Combinatorics Conference(COCOON), 559-565, 1995, Lecture Notes in Computer Science 959.


Miscellaneous Publications and Preprints

New preprints can be found here.

Qi Cheng, A New Special-Purpose Factorization Algorithm, 2002.

Qi Cheng, Hong Zhu and Jing Wu, On the Connectivity of a $n$-pancake Networks, Journal of Computer Research and Development, 7, 1-5, 1995. ( In Chinese )

Hong Zhu, Jing Wu and Qi Cheng, Enumerating All Primary Polynomials, Theoretical Computer Science in China 2, 163-170, 1994. ( In Chinese)

Qi Cheng and Hong Zhu, How Difficult is It to Obtain a Chromatic Polynomial? Proceeding of the International Workshop on Discrete Mathematics and Algorithms, 172-176, 1994.