Foundations of Computing

(Dave Barrington, Neil Immerman, Robbie Moll, Arnold Rosenberg, Hava Siegelmann, Ramesh Sitaraman, Ileana Streinu)

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 amount of computational hardware, sequential time versus reliability, and memory space versus throughput. The members 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.

Biologically Inspired Neural & Dynamical Systems Laboratory
The Biologically Inspired Neural & Dynamical Systems Laboratory aims to apply techniques developed in computer science to problems in biology and to turn insights gained from biological systems to construct better computational algorithms. A specific goal is to employ computational techniques from machine learning, such as clustering and Bayesian network modeling, to solve problems in functional genomics. Another goal of the lab is to build mathematical models of neural circuitries in the brain.

Laboratory in Kine(ma)tics and Geometry (LinKaGe)
The Laboratory in Kine(ma)tics and Geometry's research belongs to computational geometry: the investigation of algorithmic problems with geometric content. Its focus is on rigidity, flexibility and motion for constrained structures like linkages or frameworks in mechanics or robotics. In an interdisciplinary spirit, LinKaGe also considers applications to computational biology, and investigates computational methods for motion generation in molecules (in particular, proteins).

Theoretical Aspects of Parallel and Distributed Systems
Research in the TAPADS group focuses on theoretical aspects of the design and effective use of parallel and distributed computing systems and of communication networks. Issues currently being studied include load-balancing and scheduling of parallel computations, enhancing the computational power of parallel architectures using network emulations, emulating fault-free networks on possibly fault-laden ones, and efficient communication in interconnection networks and communication networks.

Theoretical Computer Science Group
Theoretical Computer Science is the quantitative and formal study of computing: which problems can be solved? what resources (for example, time or memory space) are required to solve them? Our faculty specializing in a variety of areas, including the complexity of algebraic computations, the complexity of parallel computation, the descriptive complexity of computation, and the theory of parallel and distributed processing.