First stage comprehensive exams syllabus

The written comprehensives will be offered once a year and must be attempted within four terms of the first registration. The student must write one exam from two of the following three categories:

Combinatorial enumeration suggested references

• Combinatorial Enumeration by I.P. Goulden and D.M. Jackson, J. Whiley.
  • Sections 1.1, 1.2, 2.1-2.7 and 3.1-3.4
• Enumerative Combinatorics, Volume one by R.P. Stanley, Wadsworth, Brooks, Cole.
  • Chapters one and two

Graph theory suggested references

• Graph Theory by R. Diestel, Second Edition Graduate Texts in Mathematics 173 Springer, New York, 2000.
  • Matchings (2.1, 2.2)
  • Connectivity (3.1, 3.2, 3.3)
  • Planarity (4.1-4.4)
  • Colourings (5.1, 5.2, 5.3)
  • Flows (6.3, 6.4, 6.6)
  • Turán's Theorem (7.1)
  • Ramsey's Theorem (9.1)
  • Hamiltonicity (10.1, 10.2)
  • PLUS the problems associated with the above sections
• Algebraic Graph Theory by C. Godsil and G. Royle, Graduate Texts in Mathematics 207, Springer, New York, 2001.
  • Transitivity (3)
  • Matrices and Graphs (8.1-8.8)
  • Interlacing (9.1, 9.2, 9.3)
  • Strongly Regular Graphs (10.1-10.5)
• Introduction to Graph Theory by D.B. West, Prentice Hall, Upper Saddle River, NJ 1996.
  • Connectivity (p.136-138, 4.2)
  • Ramsey's Theorem (8.3)
• Introduction to Graph Theory by R.J. Wilson, Third Edition Longman, Essex, 1985.

        Directed Graphs (7)

Continuous optimization suggested references

• Comprehensive exam syllabus for Continuous Optimization (PDF)

Discrete optimization suggested references

Combinatorial Optimization by Cook, Cunningham, Pulleyblank and Schrijver, Wiley, 1998.

• Network Flow Theory. Shortest paths; maximum flows and minimum cuts, applications, augumenting path algorithms; minimum cost flows, characterization of optimal solutions. (p. 19-62, 91-101)

• Matching. Maximum cardinality and optimal matchings, matching algorithms, matching polyhedra, optimal T-joins. (p. 127-182)

• Integer Programming and Polyhedral Theory. Linear programming, polytopes, valid inequalities, facets, separation and optimization, integral polytopes, cutting planes, branch and bound. (p. 199-240, 252-271, 325-335)

• Matroid Optimization, Matroids and the greedy algorithm, matroid polytopes, matroid intersection min-max theorem and algorithm, matroid intersection polyhedra. (p. 273-300)

• Complexity and NP-Completeness. The classes P and NP, NP-completeness. (p. 309-323)

Quantum computing suggested references

NC refers to sections in "Quantum Computation and Quantum Information" by Nielsen and Chuang. KLM refers to sections in "An Introduction to Quantum Computing" by Kaye, Laflamme, and Mosca. V and W refer to lecture notes by Umesh Vazirani and John Watrous, respectively. Alt refers to alternative reading material. 

• Mathematics of quantum information
  • Basics (NC 1.2-1.3, 2)
  • Fidelity, Ulhmann's Theorem, and trace distance (NC 9.2.1-9.2.2)
  • Quantum operations - TCP maps, Choi-Jamiokowski isomorphism, Kraus representation, isometric extension (NC 8.2, alts quant-ph/02011 (PDF)201119)
  • Quantum gates, circuit model, and universality (NC 4.2-4.5.4)

• Quantum algorithms and complexity
  • Algorithms:
    • Deutsch-Jozsa algorithm (NC 1.4, alt KLM 6.4)
    • Quantum Fourier Transform (NC 5.1, alt KLM 7.1)
    • Phase estimation (NC 5.2, alt KLM 7.2)
    • Factoring, Discrete Logarithms (NC 5.3 and 5.4.2, alt KLM 7.3-7.4)
    • Grover's search algorithm (NC 6.1-6.2 alt KLM 8)
  • Lower bounds:
    • Optimality of quantum search (KLM 9.3)
    • Black-box lower bounds (KLM 9.4-9.7)
  • Computational complexity:
    • Denitions of P, NP, BPP, PSPACE, BQP, and QMA (W 22)
    • Relating quantum and classical complexity classes:
      • P {subset of} BQP, BPP {subset of} BQP (V 3.5)
      • BQP {subset of} PSPACE (NC 4.5.5)
    • QMA-complete problems and error reduction in QMA (0804.3401 Secs V.2-3)
• Quantum cryptography
  • QKD (NC 12.6.3, 12.6.5)
  • Impossibility results (such as bit commitment) (W 19)
• Quantum error correction and fault tolerance
  • Discretization of error and theory of QEC (NC 10.3, Gottesman thesis 2.3)
  • CSS codes and stabilizer codes (NC 10.4-10.5)
  • Fault-tolerant quantum computation and the threshold theorem (NC 10.6)
• Quantum information theory and basic communication protocols
  • Superdense coding (NC 2.3), teleportation (NC 1.3.7), and resource tradeos (quant-ph/0307091 p1-2)
  • The no cloning theorem, accessible information, and Holevo's quantity (NC 12.1, quant-ph/9708019v3 Thm 1 + proof in appendix)
  • Nayak's bound (V 10.3)
  • Quantum data compression (NC 12.2)

Cryptography suggested references

• Cryptography: Theory and Practice by D. Stinson, CRC Press, third edition, 2006.
  • Classical Cryptography (1)
  • Shannon's Theory (2, omit Section 2.4.1)
  • Block Ciphers and the Advanced Encryption Standard (3)
  • Crypographic Hash Functions (4)
  • The RSA System and Factoring Integers (5)
  • Public-Key Cryptosystems and Discrete Logarithms (6)
  • Signature Schemes (7, omit Sections 7.6 and 7.7)
  • Pseudo-Random Number Generation (8, omit Section 8.4)
  • Identification Schemes (9, omit Sections 9.5 and 9.6)
  • Key Distribution (10)
  • Key Agreement (11)
  • Public-Key Infrastructure (12)
• A Course in Number Theory and Cryptography by N. Koblitz, Springer, 2nd edition, 1994.
  • Some Topics in Elementary Number Theory (1)
  • Finite Fields and Quadratic Residues (2)
  • Public Key (4, omit Sections 4.4 and 4.5)
  • Primality and Factoring (5, omit Section 5.4)
  • Elliptic Curves (6)

Old first stage comprehensive exams