REU site: Complexity Across Disciplines

This grant funds the Research Experience for Undergraduates (REU) site 'Complexity across Disciplines' at Boise State University, a nine-week program for eight students each summer. The program, hosted in the Department of Mathematics, focuses on projects related to computational complexity. The site seeks to produce cohorts of young researchers whose work and vision transcend traditional boundaries among STEM disciplines. Each cohort will engage in contemporary research problems in mathematics, with applications to cryptology, biology, and several other fields of inquiry. The program will also provide opportunities for REU students to participate in outreach activities targeting K-12 students in the region. Students from rural communities with limited opportunities will have one-on-one exposure to highly motivated STEM students from across the nation. The site offers, in collaboration with other summer undergraduate research programs at Boise State University, a rich array of professional and interdisciplinary development events.

The nature of computing and complexity has expanded from the academic realm to the practical arena through great strides made in the scientific understanding of basic processes of life, significant advances in information processing through the growth of the internet, and automation of basic daily tasks. The research projects are motivated by a quest for efficient search or sorting algorithms and for efficient information security tools. The mathematical foundations for these projects include algebraic structures, combinatorial structures, and game theory. Each project has deep connections with significant open problems in mathematics, and could lead to discoveries of importance to the security of current commercially used cryptosystems and to data mining. The idea of examining certain genomic rearrangement processes from a game-theoretic point of view is new, has inherent value as a mathematical exploration, and has the potential to clarify observed phenomena in natural rearrangement processes.