Foundations of Computing

[Overview]   [Faculty]   [Projects]   [Courses]

Foundations of Computing addresses our curiosity about possibilities and fundamental limitations of computing devices. Recurring themes in our research are fundamental questions about algorithms and complexity. We study approximation, geometric, distributed, parallel, quantum, and randomized algorithms, and a plethora of beautiful applications.

We exchange ideas in the weekly Parasol and Quantum Computing seminars, and organize many other activities and events. You can find the announcements in the weekly events.

Faculty

Nancy Amato   (Research Interests: Motion Planning, Robotics, Computational Geometry, Virtual Reality, Computational Biology/Chemistry, Parallel and Distributed Computing, Parallel Algorithms, Performance Modeling)

Jianer Chen   (Research Interests: Computational Optimization and Complexity, Graph Theory and Algorithms, Parallel Processing and Networking, Computer Graphics)

Don Friesen   (Research Interests: Algorithm Analysis, Parallel Algorithms, Artificial Intelligence, Neural Networks)

John Keyser   (Research Interests: Geometric Computing, Graphics and Visualization, Simulation and Modeling, Computer Algebra)

Andreas Klappenecker   (Research Interests: Quantum Computing, Algorithm Analysis, Cryptography)

Bruce McCormick   (Research Interests: Computer vision, neural networks, brain mapping)

Paul Nelson   (Research Interests: Mathematical analysis, parallel numerical analysis)

Scott Pike   (Research Interests: Distributed Computing, Fault Tolerance, Stabilization, Dynamic Reconfiguration)

Lawrence Rauchwerger   (Research Interests: Parallelizing Compilers, Architectures for Parallel Computers)

Sing-Hoi Sze   (Research Interests: Bioinformatics/Computational Biology)

Jennifer Welch   (Research Interests: Theory of Distributed Computing, Algorithm Analysis, Distributed Systems, Mobile Ad Hoc Networks, Distributed Data Structures)

Projects

Efficient Massively Parallel Adaptive Algorithm for Time-Dependent Transport on Arbitrary Spatial Grids, DOE
PIs: Marvin Adams, Nancy Amato, Paul Nelson, Lawrence Rauchwerger

ITR/AP: A Motion Planning Approach for Protein Folding Simulation, NSF
PIs: Nancy Amato, Lawrence Rauchwerger, Ken Dill (UCSF)

Parameterized Computation and Applications, NSF
PI: Jianer Chen

ITR: Accurate and Robust Operations on Curved Geometry, NSF
PI: John Keyser

Exploring the Brain Forest, THECB ATP
PIs: John Keyser, Bruce McCormick

CARGO: Degeneracy Detection for Curved Solids, NSF
PIs: John Keyser, Maurice Rojas

CAREER: Design of Efficient Quantum Algorithms, NSF
PI: Andreas Klappenecker

Efficient Decoherence Control Algorithms, NSF
PI: Andreas Klappenecker

Quantum Computation, TITF
PIs: Andreas Klappenecker, Goong Chen, Berthold-Georg Englert, Suhail Zubairy

ITR/SY: SmartApps: An Application Centric Approach to Scientific Computing, NSF
PIs: Lawrence Rauchwerger, Nancy Amato

Exact Computational Biology Algorithms with Small Parameters, NSF
PIs: Sing-Hoi Sze, Jianer Chen

Self-Stabilizing Group Communication for Mobile Environments, NSF
PIs: Jennifer Welch, Nancy Lynch (MIT)

Courses

CPSC 111. Computer Science Concepts and Programming.
CPSC 211. Data Structure & Implementations.
CPSC 311. Analysis of Algorithms.
CPSC 433. Formal Languages and Automata.
CPSC 440. Algorithmic Aspects of Quantum Computing.
CPSC 441. Computer Graphics.
CPSC 620. Computational Geometry.
CPSC 627. Theory of Computability.
CPSC 626. Parallel Algorithm Design and Analysis.
CPSC 629. Design and Analysis of Algorithms.
CPSC 637. Complexity Theory.
CPSC 641. Computer Graphics.
CPSC 645. Geometric Modeling.
CPSC 668. Distributed Algorithms and Systems.
CPSC 669. Computational Optimization.
CPSC 689. Computational Biology.
CPSC 689. Algorithmic Aspects of Quantum Computing.
CPSC 689. Randomized Algorithms.
CPSC 689. Robust Numerical and Geometric Computation.