Algorithms and Cryptography

abstract image

Overview

The Algorithms and Cryptography group explore the limits of computation in developing algorithms and protocols that provide provable performance guarantees such as correctness and privacy. We have strengths in developing algorithms that take advantage of geometric and topological properties to solve classic problems such as maximum flow and network design as well as more newly developed, applied problems, for example, in routing. We also develop cryptographic tools that allow sensitive data to be used in arbitrary computations while simultaneously maintaining privacy.

Research Thrusts

Algorithms

  • Approximation Algorithms
  • Graph Algorithms
  • Computational Geometry & Topology

Cryptography & Complexity

  • Computing on encrypted / hidden data
  • Protocols for secure computation
  • Computational complexity

Related Courses

  • CS 321: Introduction to the Theory of Computation
  • CS 325: Analysis of Algorithms
  • CS 420/520: Graph theory with applications to CS
  • CS 419/519: Introduction to Cryptography
  • CS 519: Advanced Cryptography
  • CS 515: Algorithms and Data Structures
  • CS 517: Theory of Computation
  • CS 523: Advanced Algorithms

Software Downloads

  • Vamanos for web-based algorithm visualization.
 

Faculty

Glencora Borradaile

Glencora Borradaile
Approximation algorithms; planar graphs; combinatorial algorithms

Mike Rosulek

Mike Rosulek
Secure computation; cryptography

Amir Nayyeri

Amir Nayyeri
Computational geometry; computational topology

 
 
 

Research Partners

Industry & Other Organizations

Bell Labs Google logo Mentor Graphics Pacific Northwest National Laboratory logo

Universities

Brown University University of Calgary logo University of California - Irvine logo Carnegie Mellon University logo
Columbia University logo University of Illinois at Urbana-Champaign MIT logo University of Maryland
Ohio State University logo Saint Louis University logo University of Texas - Austin logo Toyota Technological Institute at Chicago logo
Tsinghua University logo Virginia Commonwealth    

Selected Projects

Understanding and advancing network design in planar domains
(Borradaile)

  • Designing more accurate approximation algorithms for optimization problems in planar and related domains
  • Generalizing planar domains and characterizing near-planar domains

Using density for network analysis
(Borradaile)

  • Decomposing networks according to regions of uniform density
  • Modeling networks as layers of uniform density

Getting the most out of secure computation
(Rosulek)

  • Developing new secure computation protocols aimed at bridging the gap between theory and practice