Williams Company Foundation Presidential Professor
Phone: (405) 325-1017
Office: Devon Energy Hall Room 254
Ph.D., Computer Science
University of Southern California
M.S., Computer Science
Fudan University, Shanghai, China
B.S., Computer Science
Nankai University, Tianjin, China
Experience and Awards
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.
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.
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.