Theoretical Computer Science

Research on the foundations of computing employs mathematical tools to advance our understanding of computation on both man-made computers and networks as well as in natural environments including the human brain. Members of this research group have made fundamental contributions to the understanding of computational complexity. They seek to further understand the tradeoffs between certain computational resources including parallel time versus the amount of computational hardware, sequential time versus reliability, and memory space versus throughput. Researchers also apply theoretical tools to efficiently solve real technological problems, including how to deliver content efficiently and cost-effectively on the Internet, how to automatically check that software is meeting certain efficiency and correctness requirements, how to schedule computations efficiently in modern computing environments (e.g., clusters of workstations or computational grids), and how to coordinate ensembles of simple robots to cooperate in the performance of complex tasks.