The Foundations of Computer Science Track
The Foundations of Computer Science track is intended for students who wish to develop state of the art knowledge
of the theoretical foundations of Computer Science. The theory of computation plays a crucial role in providing solid
foundations for all areas of Computer Science, including systems, artificial intelligence, security, and circuit design.
This track will help you develop leading-edge knowledge of theoretical Computer Science and its applications.
Track Advisor
Prof. Rocco Servedio is the advisor
for Masters students following this track. E-mail: rocco@cs.columbia.edu.
Overall Requirements
Students must complete at least a total of 30 graduate credits:
1. Fulfill the 12-credit core breadth requirement. One of the core breadth requirements must be COMS W4231. In addition,
COMS W3261 or past equivalent is a required prerequisite.
2. One required course: COMS W4236.
3. One course chosen from the "Electives I" list: COMS W4203, COMS W4205, COMS W4241, COMS W4252, COMS W4261,
or COMS W4281.
4. At least 9 additional credits from the "Electives II" list, excluding the course chosen from the "Electives I"
list to satisfy (3) above. At least 6 of the credits must come from 6000-level courses.
5. Remaining credits from any qualifying graduate course (4000 and 6000 level). At least 3 of these credits must
be in COMS.
Core Breadth Requirements:
Students must complete at least four Core courses out of the following six:
COMS W4115: Programming Languages and Translators
COMS W4118: Operating Systems
COMS W4156: Advanced Software Engineering
CSOR W4231: Analysis of Algorithms
COMS W4701: Artificial Intelligence
CSEE W4824: Computer Architecture
Prerequisite
COMS W3261: Computer Science Theory (not for Masters credit)
Required Core Breadth Course
COMS W4231: Analysis of Algorithms
Required Track Course
COMS W4236: Introduction to Computational Complexity
Track Program: Electives I
Candidates are required to complete one (1) of the following courses:
COMS W4203: Graph Theory
COMS W4205: Combinatorial Theory
COMS W4241: Numerical Algorithms and Complexity
COMS W4252: Computational Learning Theory
COMS W4261: Introduction to Cryptography
COMS W4281: Quantum Computing
Track Program: Electives II
Candidates are required to complete 9 credits from the following list excluding the course already taken.
At least 6 credits must be at the 6000 level
COMS W4203: Graph Theory
COMS W4205: Combinatorial Theory
COMS W4241: Numerical Algorithms and Complexity
COMS W4252: Computational Learning Theory
COMS W4261: Introduction to Cryptography
COMS W4281: Quantum Computing
COMS E6291: Theoretical Topics in Computer Science
COMS E6998: Advanced Topics in Cryptography
COMS E6253: Computational Learning Theory II
COMS E6998: Advanced Topics in Complexity Theory
COMS E6901: Projects in Computer Science
ELEN E6717: Information Theory
COMS E6232: Analysis of Algorithms II
CSEE W6180: Performance Analysis
IEOR E6610: Approximation Algorithms
SIEO W4150: Introduction to Probability and Statistics
IEOR E4004: Introduction to Operations Research - Deterministic Models
IEOR E4407: Game Theoretic Models of Operation
IEOR E6603: Combinatorial Optimization
IEOR E6606: Advanced Topics in Network Flows
ELEN E4710: Introduction to Network Engineering
ELEN E6718: Algebraic Coding Theory
ELEN E6970: Resource Allocation and Networking Games
*Note: The list of electives may be updated to reflect changes in the schedule of course offerings.