Algorithms and Complexity Concentration

The goal of the Algorithms and Complexity concentration is to give 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 semindefinite programming.
  • The ability to recognize flaws in ill-formed proofs.
  • The ability to formulate new questions about the field.

Course Requirements

The curriculum will consist of one required course (Computational Complexity, 15-455) 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.

The initial list of courses is:

  • Computational Discrete Math (15-354)
  • Computational Geometry (15-456) (prereq. 15-451)
  • Discrete Differential Geometry (15-458) (prereq. 21-259)
  • Introduction to Cryptography (15-503)
  • Theorist Toolkit (15-751) (sug. prereq 15-451)
  • Special Topics in Cryptography (15-827)
  • Advanced Algorithms (15-850) (prereq 15-451)
  • Algorithms in the Real World (15-853) (sug. prereq 15-451)
  • Analytical Performance Modeling and Design (15-857)Machine Learning Theory (15-859B)
  • Quantum Computation and Quantum Information (15-859BB)
  • Algorithms for Big Data (15-859CC) (sug. prereq 15-451)
  • Spectral Graph Theory (15-859N) (sug. prereq 15-451)
  • Coding Theory (15-859Y)
  • Algorithm Superpower Randomization (15-859Z)
  • Truth Justice and Algorithms (15-896) (sug. prereq 15-451)
  • Combinatorics (21-301)
  • Graph Theory (21-484)
  • Random Graphs (21-801)
  • Integer Programming (47-830, Mini)
  • Linear Programming (47-834, Mini)
  • Graph Theory (47-835, Mini)
  • Advanced Graph Theory (47-836, Mini)
  • Convex Optimization (47-851, Mini)
  • Special Topics in Combinatorial Optimization (47-853, Mini)

The prerequisites (prereq.) are those beyond the overall concentration prerequisites listed below. The notation “sug. prereq.” means suggested prerequisite. The graduate algorithms course (15-750) does not count since it is not sufficiently different than 15-451. A student can also use a senior thesis or research-based independent study as one of the elective courses (for 12 units). The topic must be related to algorithms and complexity, and approved by the director. An independent study must be for at least 12 units, and there must be a substation paper writeup on the research topic, and a poster or other presentation.

The complexity course will be offered every semester. Furthermore at least two elective courses will be offered every semester.

The choice of elective courses will be posted prior to registration during the previous semester.

Prerequisites

The courses 15-210, 15-251, 15-451, 21-241 and one of 15-259, 21-325 or 36-218 are prerequisites to the concentration. It is expected that all students will start the concentration after having finished all but 15-451.

Double Counting

The concentration will require that 3 courses (at least 27 units) are not double counted with any other requirements of any Major, Minor, or other concentration the student is pursuing.

Management

The director of the Algorithms and Complexity concentration is TBD. Courses in the list of electives will be approved by the director on a yearly basis under consultation of the algorithms and complexity group (to help evaluate the relevance of the courses) and the Assistant Dean (to help flag any logistical issues). Any special requests by a student for counting a course out of the list, will go to the director. The director will also approve any research units.