CAREER: Research in Algorithmic Theory of Self-Assembly

自组装是简单的物体自发地组装成复合体的过程。预计它最终将成为原子和分子层面的一项重要技术。可编程自组装的研究发展到了必须从数学上理解它才能充分利用这一新工具的阶段。本研究的目的是研究自组装的计算方面。这个项目的目标包括：(1)解决瓦片组装模型中的具体问题，包括但不限于寻找最小瓦片集问题(MTSP)的近似算法和描述形状语言。(2)探索不同的自组装模型，这将给出更准确的实验结果抽象，并将反映分子/DNA计算中的大规模并行性。(3)研究算法自组装与经典计算理论之间的联系。特别是通信理论和资源受限的Kolmogorov复杂性。这个职业项目将把教学活动整合到自组装研究中。PI将提供分子计算和生物信息学等密切相关领域的研究生水平的课程，并在普通理论课程中向本科生和研究生介绍这项研究。该项目将在教学中采用主动学习技术。希望该项目将有助于理解自组装的工程能力，并将当前的研究信息传播给学生。

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 andmolecules. The development of researches in programmableself-assembly is reaching the stage that we haveto understand it mathematically in orderto 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 tofinding an approximation algorithm for the MinimumTile Set Problem (MTSP)and characterizing the shape languages.(2) Exploring different modelings of self-assembly, whichwill 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 theoryof computation, especially the communication theoryand the resource-bounded Kolmogorov complexity.This CAREER project will integrate teaching activity into the research of self-assembly.The PI will offer graduate level courses in molecular computing and closely-related fields such as bioinformatics, and introduce the researchto 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 understandingthe engineering power of self-assembly, and to disseminatingthe current research information to students as well.