AF: EAGER: Randomization and Parallelization in Algorithmic Self-Assembly

在这个项目中，pi探索了算法自组装的各种理论模型，以及新模型的开发，同时吸引了一些本科生和研究生参与研究活动。自组装是指简单的、无组织的部件自动组合成更大、更复杂的结构的过程。这一过程在自然界中是丰富的，是生物有机体构建的关键潜在机制。研究人员正在转向自组装技术，以设计更小、更复杂和精确的纳米级器件，并将其作为纳米技术的新兴基础工具。医疗保健、计算和工程领域可能发生的革命性变化使其成为一个令人兴奋和重要的研究领域。这个项目的重点是算法自组装，其中系统的对象通过模拟复杂计算的局部相互作用组装，以有效地组装目标形状和图案。充分理解自组装系统的力量，以及如何控制它们，为在纳米尺度上精确有效地操纵物质设计分子算法提供了可能性。为实现这一目标而开发的模型和理论与实验现实密切相关，这是本项目的重点。pi探索了各种已建立的基于瓷砖的自组装理论模型，以及由当前实验技术驱动的新模型的开发。这包括检查瓷砖自组装系统中的具体问题，以及在不同模型中创建和使用随机性。利用随机性和自组装系统的并行计算可以为许多有用的函数提供新颖的解决方案和有效的运行时间。这个项目的技术方面侧重于随机化和并行化的工具在瓷砖自组装理论的背景下。具体操作方法如下：pi考虑了浓度稳健瓦片系统的设计，其中随机抽象瓦片组合系统被转换为等效系统，其组合的概率分布在对抗性选择的瓦片种类浓度分配上保持不变。这个方向的目标是生成一个工具箱，用于将瓷砖系统转换为对集中选择具有鲁棒性的近似等效系统。pi进一步研究了这种鲁棒随机系统在经典计算问题的并行解决中的应用，包括排序、素数测试和随机布尔电路的一般模拟。pi还研究了与h手自组装相关的复杂性，其中多达h个预建组件可以在单个步骤中组合。最后，VersaTile和Nubot仿真软件的持续开发和改进也是这个项目的一个重要方面。这些系统用于研究中的验证和教育目的，允许用户轻松创建，测试，修改和可视化自组装过程。与所描述的理论工作相结合，该项目的一个主要目标是增加德克萨斯大学格兰德谷分校学生的研究参与度，并增加参加计算机科学博士课程的本科生和硕士生的吞吐量。该项目包括支持本科生和研究生的研究助理奖学金，以及由pi主持的一系列成功的研究研讨会的扩展，重点是吸引本科生的参与和合作。德克萨斯大学格兰德谷分校是一所少数族裔大学，拥有约3万名学生，其中90%是西班牙裔学生，55%是女性学生。由于这些人口统计数据，该项目提供了一个难得的机会，对扩大计算机科学领域中代表性不足的少数群体的参与产生重大影响。

In this project the PIs explore various theoretical models of algorithmic self-assembly, as well as the development of new models while engaging a number of undergraduate and graduate students in research activities. Self-assembly is the process by which simple, unorganized components autonomously combine to form larger, more complex structures. This process is abundant in nature and is a key underlying mechanism for the construction of biological organisms. Researchers are turning to self-assembly technology for the design of ever smaller, more complex, and precise nanoscale devices, and as an emerging fundamental tool for nanotechnology. The possible revolutionary changes to healthcare, computation, and engineering make this an exciting and important area of research.The focus of this project is algorithmic self-assembly in which the objects of a system assemble through local interactions that simulate sophisticated computation to efficiently assemble target shapes and patterns. Fully understanding the power of self-assembly systems, and how to control them, presents the possibility of designing molecular algorithms for precise and efficient manipulation of matter at the nanoscale. Developing models and theory towards this goal that are closely tied to experimental reality is the focus of this project. The PIs explore various established tile-based theoretical models of self-assembly, as well as the development of new models motivated by current experimental technology. This includes examining specific problems within tile self-assembly systems, and the creation and use of randomness within different models. Using randomness along with the parallel computation of self-assembly systems should allow for novel solutions and efficient running times for many useful functions.Technical aspects of this project focus on the tools of randomization and parallelization in the context of tile self-assembly theory. Specific directions are as follows. The PIs consider the design of concentration robust tile systems in which randomized abstract tile assembly systems are converted into equivalent systems whose probability distribution over assemblies is maintained over adversarially chosen concentration assignments of tile species. The goal of this direction is to generate a toolbox for general conversion of tile systems into approximately equivalent systems that are robust to concentration choice. The PIs further examine the application of such robust randomized systems for the parallelized solution to classic computational problems including sorting, primality testing, and the general simulation of randomized boolean circuits. The PIs also study complexities related to h-handed self-assembly in which up to h prebuilt assemblies may combine in a single step. Finally, the continued development and improvement of the VersaTile and Nubot simulation software are also an important aspect of this project. These systems are used for verification and educational purposes in research allowing users to easily create, test, modify, and visualize the self-assembly process.In tandem with the theoretical work described, a major goal of this project is to increase research participation among students at the University of Texas - Rio Grande Valley and increase the throughput of undergraduate and masters students who enroll in Ph.D. programs in Computer Science. This project includes support for undergraduate and graduate student research assistantships, as well as the extension of a successful ongoing series of research seminars, hosted by the PIs, focused on attracting undergraduate student participation and co-authorship. The University of Texas - Rio Grande Valley is a minority-serving institution that has about 30,000 students with a 90% Hispanic and 55% female student population. Due to these demographics, this project offers a rare opportunity to make a substantial impact on broadening participation among under-represented minority groups in the field of Computer Science.