Ryan O'Donnell, Concentration Director
Location: GHC 7213

Amy Weis, Concentration Coordinator
Location: GHC 4115

Algorithms and Complexity Concentration

This concentration is available to SCS students only.

The goal of the Algorithms and Complexity concentration is to give SCS students a deep background in the theory of computation as it relates to algorithms and computational complexity. The expectation is that students who complete this concentration will have the background to pursue topics at the PhD level at any top program in the country. Furthermore we expect the reasoning skills gained as part of this concentration could be a significant help in a wide variety of positions in industry.

The concentration is designed to be reasonably flexible covering a wide area of topics within the area of algorithms and complexity. This includes central topics within the area such as complexity theory, and algorithms, but also includes theory as used in areas such as Computational Geometry, Graph Theory, Cryptography, Machine Learning, Algorithms for Large Data, Error Correcting Codes, and Parallel Algorithms.

Common themes of all courses covered by the concentration are the following:

• Clearly defined formalisms of the subject matter.
• A substantial component involving rigorous mathematical analysis, including proofs.
• Abstracting away from specific applications to a more general context.
• Relating algorithms and/or complexity of computation to a variety of complexity measures such as time, space, communication, or information content.

Any given course does not have to exclusively cover these themes and can, for example, also cover experimental aspects of algorithms, or examples applied to quite specific applications.

Learning Objectives

We do not expect students to have high proficiency in all the examples listed, but to gain at least some proficiency from each category.

• The ability to take a loosely defined problem and clearly pose it as a well defined problem specification.
• The understanding of several advanced algorithms beyond what is covered in the core.
• The appreciation a variety of models for bounding resources, such as information theory, space complexity, parallel complexity, communication complexity, proof complexity, query complexity, and hardness of approximation.
• The ability to understand and apply a variety of advanced algorithmic techniques and proof techniques, such as Lovasz Local Lemma, Johnson Lindenstrauss, Chernoff Bounds, sparsification, expanders, probabilistic method, regret bounds, spectral graph theory, fixed parameter tractability and semi-indefinite programming.
• The ability to recognize flaws in ill-formed proofs.
• The ability to formulate new questions about the field.

Curriculum

Prerequisites

Course Requirements

The curriculum consists of one required course and at least three elective courses. The three elective courses must sum to at least 30 units. The elective courses will vary from year to year.

Required Course:

Electives (at least three courses with a total of 30 units or more):

Students can apply one semester of a senior honors research thesis or research-based independent study in a topic related to this concentration, as approved by the concentration director/advisor, as one of the elective courses for this concentration. This research must have a significant communication component, including a paper or technical report, and a poster presentation. Any research course can count for at most 12 units toward the concentration and can count for at most one elective. 

The choice of available elective courses will be posted prior to registration each semester.

Double Counting