Qi Cheng

Williams Company Foundation Presidential Professor

Email: qcheng@ou.edu
Phone: (405) 325-1017
Office: Devon Energy Hall Room 254

Education
Ph.D., Computer Science
University of Southern California
M.S., Computer Science
Fudan University, Shanghai, China
B.S., Computer Science
Nankai University, Tianjin, China

Research Focus

Theoretical computer science, DNA/molecular computing, cryptography and computational number theory.

Experience and Awards

Williams Company Foundation Presidential Professor
Associate Professor, University of Oklahoma
Assistant Professor, University of Oklahoma
Assistant Lecturer, Fudan University
ACM (Member)

NSF Career Award
Title: Research in Algorithmic Theory of Self-Assembly

NSF Career Award Summary
Self-assembly is the process by which simple objects spontaneously assemble into complexes. It is expected to ultimately become an important technology at the level of atoms and molecules. The development of research in programmable self-assembly is reaching the stage in which we have to understand it mathematically in order to take full advantage of this new tool. The goal of this research is to study the computational aspects of self-assembly. The objectives of this project includes: (1) Solving concrete problems in the Tile Assembly Model, including but not limited to finding an approximation algorithm for the Minimum Tile Set Problem (MTSP) and characterizing the shape languages. (2) Exploring different modelings of self-assembly, which will give a more accurate abstraction of the experimental results and will reflect the massive parallelism in molecular/DNA computing. (3) Studying the connections between the algorithmic self-assembly and the classical theory of computation, especially the communication theory and the resource-bounded Kolmogorov complexity. This CAREER project will integrate teaching activity into the research of self-assembly. The Principal Investigator will offer graduate level courses in molecular computing and closely-related fields such as bioinformatics, and introduce the research to undergraduate and graduate students in general theory courses. This project will adopt the active learning techniques in teaching. It is expected that the project will contribute to understanding the engineering power of self- assembly, and to disseminating the current research information to students as well.

Biography

Dr. Qi Cheng is a Williams Company Foundation Presidential Professor in the School of Computer Science at the University of Oklahoma, where he joined in 2001. He received his PhD in Computer Science from University of Southern California in 2001. His research interests are in the areas of theoretical computer science, DNA/molecular computing, cryptography and computational number theory. He has published over 30 research articles in journals and conference proceedings.

Selected Projects

NSF, AF: Medium: Collaborative Research: Sparse Polynomials, Complexity, and Algorithms, 2014–2016.
NSF, Zero testing and sign determination of algebraic numbers, $198K, 2009 -- 2012.
NSF, Collaborative Research: Complexity and Algorithms of Decoding Algebraic Codes; $197K, 2009--2012.
NSF CAREER, “Research in Algorithmic Theory of Self-Assembly,” 2003-2008.

Selected Publications

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.“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
“Derandomization of Sparse Cyclotomic Integer Zero Testing,” FOCS 2007, pp. 74-80. Journal version appeared in Theory of Computing Systems.
“On the List and Bounded Distance Decodability of the Reed-Solomon Codes,” SIAM journal on Computing, 37 (1), pp. 195-209. Special issue on FOCS 2004 (with Daqing Wan).
“Primality Proving via One Round in ECPP and One Iteration in AKS,” Journal of Cryptology, 20(3), pp. 375-387.
“Combinatorial optimization problems in self-assembly,” 34th Annual ACM Symposium on the Theory of Com- puting(STOC), 2002 (with Len Adleman, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo Moisset de Es- panes and Paul Rothemund).
“Running Time and Program Size for Self-assembled Squares,” 33th Annual ACM Symposium on the Theory of Computing(STOC), 2001 (with Leonard Adleman, Ashish Goel and Ming-Deh Huang).