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.
Qi Cheng and Daqing Wan, Complexity of Decoding Positive-Rate Reed-Solomon Codes, Proceedings of ICALP 2008.
Qi Cheng, Derandomization of Sparse Cyclotomic Integer Zero Testing, FOCS 2007, Pages 74--80.
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 to appear 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.
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.