One can argue that theoretical computer science (tcs) is an essential part of almost everything that we do in computer science and it plays an important role in the growing connections between computer science and other disciplines. This project is aimed at exploring the connections of tcs both throughout computer science and to other fields of research. The vehicle for exploration will be a series of workshops carried out over a period of three years and involving a large cross-section of the theory community in partnership with individuals outside that community.
Intellectual Merit The workshops that we plan are organized into several broad themes that span a wide variety of topics: (1) Algorithmic Decision Theory, (2) New Applications of combinatorial Optimization, (3) Autonomic Computing and Self-Healing, Self-Adapting Systems, (4) Discrete Random Systems, (5) New Tools for Bioinformatics/Computational Biomedicine, and (6) TCS and Neuroscience. Under Theme 1, there will be workshops on: Efficient Representation and Elicitation of Information in Decision Making and on Decision Problems in Algorithmic Forensic Linguistics. Theme 2 workshops will be on Combinatorial Optimization Approaches in Computational Biology, Oblivious Routing and Robust Optimization, Experimental Analysis of Algorithms in Combinatorial Optimization, and Challenging Industrial Applications of Combinatorial Optimization, while Theme 3 workshops will be on Fundamental Science of Self-Managing Systems and on Self-Healing Systems. Under Theme 4, planned workshops are on Random Structures and Randomized Algorithms and on From Heuristics to Rigor in Physical Arguments." Theme 5 workshops are on Trends in Bioinformatics: The Interplay between Experimental Biology and Theoretical Computer Science, Machine Learning Techniques in Bioinformatics, Clustering problems in Biological Networks, and Discrete Mathematical Problems in Computational Biomedicine. Finally, in Theme 6, we will have workshops on Quantitative Neuroscience and on Neural Imaging.
Broader Impacts The ideas developed in this project will have impact on a myriad of fields and create cross-disciplinary connections. A visitor program will encourage senior and junior researchers, including students, to participate in collaborative research spawned by the workshops. Each workshop will have a fund for support of graduate students and postdocs amd workshops will have a substantial educational component through talks of a tutorial/expository nature. The topic lends itself well to undergraduate research and participating faculty will coordinate topics with an undergraduate research program (REU program) already in existence, one that caters to students from all over the U.S. To give the project widespread dissemination, each workshop will have a website with relevant references, problems, and copies of presentations that can make it a resource for a large community. The project is expected to have a long-term impact well beyond its three year duration since the workshop, visitor, and dissemination components of the project will allow the ideas developed to reach hundreds of people nationwide and worldwide.
