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

点击翻译按钮获取中文摘要

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.