Semester:
Offered:
Class: SC105, MW 1500-1615
Office hours: MW 1300-1500, SC518
1. Description: In this course, mathematical aspects of computational complexity theory will be broadly covered. We shall start with basics of complexity theory (Turing machines, various notions of complexity and NP completeness), discuss other computation models and intractability results, and explore algebro-geometric & representation theoretic approach to P vs NP. The topics are intricately related but can be learned separately. The goal is to introduce the audience and give them basic knowledge on broad range of topics related to computational complexity (instead of giving an in-depth treatment of one): Understanding a wide spectrum of subjects leads to a deeper understanding and appreciation of the core issues. I also hope that the audience would find something exciting and decide to explore/investigate on their own.
The course largely consists of four parts:
- Basic complexity theory: Classical computation models such as Turning machines, Boolean circuits, probabilistic algorithms and NP completeness (Cook-Levine Theorem)
- Computation models: Blum-Smale-Shub model, quantum computation, continuous time system.
- Intractability & unsolvability: Diophantine simulation of Turing machines, Hilbert’s 10th problem and algorithmic unsolvability of various problems
- Geometric complexity theory (GCT): Algebro-geometric and representation theoretic approach to P vs NP
The latter two topics requiring more mathematical knowledge and maturity. GCT will use basic notions and results in algebraic geometry and representation theory. Discussion of computation models will involve basic knowledge on dynamical systems, probability and analysis (differential equations & Fourier analysis, in particular).
2. Prerequisites: No knowledge of computer science is assumed. Knowledge on basic algebraic geometry and representation theory will be helpful to follow the materials on GCT (geometric complexity theory): Varieties, algebraic groups, orbits/orbit closures, homogeneous spaces, representations of algebraic groups (especially general linear groups and symmetric groups), quotients of varieties by algebraic groups (Geometric Invariant Theory) and some parameter spaces such as Chow varieties may come up in the discussion. But GCT will be discussed in the last weeks, and we will choose topics carefully according to the level of knowledge of the audience. Also, definitions and FACTS will be given so that one can follow (if not appreciate) the discussion with reasonable intellectual satisfaction.
If you have no knowledge of algebraic geometry, you are encouraged to read the Lectures 1 and 2 of Algebraic Geometry: A first course by Joe Harris or the first four sections of Algebraic Geometry by R. Hartshorne.
If you have no knowledge of representation theory, you are encouraged to read Lectures 7, 8, 11, (and 12 &13 if possible), 14 of Representation theory: A first course by W. Fulton and J. Harris. An overview of the representations of the general linear group (and other relevant representation theory) will be given in class.
If you have some working knowledge on algebraic geometry and want to read about geometric invariant theory, a good place to start is “Introduction to moduli problems and orbit spaces” by Peter Newstead. Such effort is certainly not necessary for the purpose of taking this course since basic notions will be covered in class.
If you want to do some reading ahead on specific topics:
Basic complexity theory:
Sections 1, 2 of Computers and Intractability by Michael. R. Garey and David S. Johnson (Freeman)
Sections 1, 2, 3 of Classical and Quantum Computation by A. Kitaev, A. Shen, M. Vyalyi (AMS);
Quantum computation:
Sections 6 of Classical and Quantum Computation by A. Kitaev, A. Shen, M. Vyalyi (AMS);
A very brief introduction to quantum computing and quantum information theory for mathematicians, J.M. Landsberg (Texas A&M University, College Station, TX, USA), arXiv:1801.05893 [math.HO]
BSS model of computation:
Chapter 3 of Complexity and Real Computation by L. Blum, F. Cucker, M. Shub, S. Smale (Springer)
Geometric Complexity Theory:
Geometric complexity theory: an introduction to geometers, J.M. Landberg, arXiv:1305.7387 [math.AG]
3. Text: I will draw materials from the following books and papers (and some others). Electronic and/or photographic copy of the material will be distributed, and lecture notes will be made available.
Books:
- Basic Complexity Theory
Computers and Intractability by Michael. R. Garey and David S. Johnson (Freeman)
- Computation models
Complexity and Real Computation by L. Blum, F. Cucker, M. Shub, S. Smale (Springer)
Classical and Quantum Computation by A. Kitaev, A. Shen, M. Vyalyi (AMS)
Principles of Quantum Computation and Information - Vol.1: Basic Concepts New edition Edition by Giuliano Benenti, Giulio Casati, Giuliano Strini (World Scientific)
- Intractability & Unsolvability
Hilbert’s Tenth Problem by Yuri Matiyasevich (The MIT Press)
- GCT
Completeness and reduction in algebraic complexity theory by Peter Bürgisser (Springer)
Papers*:
- Computation models
On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines by Blum, Lenore; Shub, Mike; Smale, Steve (Bull. AMS, 1989)
Analog computation with continuous ODEs by Michael S. Branicky (IEEE, 1994)
A Survey of Continuous-Time Computation Theory by Pekka Orponen, in Advances in Algorithms, Languages, and Complexity (Springer)
A Theory of Complexity for Continuous Time Systems by Asa Ben-Hur, Hava T. Siegelmann and Shmuel Fishman, journal of complexity 18, 51_86 (2002)
Computability with polynomial differential equations by Daniel S. Graça, Manuel L. Campagnolo, Jorge Buescu, Advances in Applied Mathematics 40 (2008)
- Intractability & Unsolvability
Proof of recursive unsolvability of Hilbert’s tenth problem by Y. Matiyasevich and J. P. Jones (Amer. Math. Monthly, 1991)
On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP≠P?''. By Shub, Michael(1-IBM); Smale, Steve(PRC-CHK),
Duke Math. J. 81 (1995), no. 1, 47–54 (1996).
Complexity of Bézout's theorem. I. Geometric aspects. By Shub, Michael(1-IBM); Smale, Steve(1-CA), J. Amer. Math. Soc. 6 (1993), no. 2, 459–501.
- Geometric Complexity Theory
An introduction to geometric complexity theory J.M. Landsberg (Texas A&M University, College Station, TX, USA), https://arxiv.org/pdf/1509.02503.pdf
Geometric complexity theory: an introduction to geometers, J.M. Landberg, arXiv:1305.7387 [math.AG]
An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP by Peter Buergisser, J.M. Landsberg, Laurent Manivel, Jerzy Weyman, arXiv:0907.2850 [cs.CC]
* an incomplete list
4. Ambitious Tentative Weekly Schedule
- Introduction, Turing Machine and TM algorithm, probabilistic algorithm, undecidability, non-deterministic TM
- Complexity and classes P & NP, reduction of problems, universal machines, NP completeness (Cook-Levine Theorem)
- Hillbert’s 10th problem: arithmetisation of register machines, exponential relations as Diophantine relations, proof of Hilbert 10th
- Undecidable problems in number theory & algebraic geometry
- Computation over a ring (Blum-Smale-Schub model)
- Intractability & NP completeness in BSS theory
- Classical circuit model (Boolean circuits), quantum computation (quantum circuit), quantum complexity classes, quantum analog of P vs NP, Grover search algorithm
- Quantum Fourier Transformation, phase estimation, applications: period finding problem, integer factorization
- CTS (Continuous Time System) model, analog computation (GPAC), simulation of Turing machine by continuous ODE
- Simulation of TM by analytic & polynomial ODE, computational complexity of CTS
- Universality of determinant, permanent VS determinant conjecture, quasi-homogeneous varieties associated with determinant and Mulmuley-Sohoni conjecture
- Representations of general linear groups & symmetric groups, Schur-Weyl duality, Kronecker coefficients
- Coordinate rings of orbit closures as representations, stability (in the sense of GIT), stability of the determinant
- Partial stability, irreducible modules in the coordinate ring of the orbit closures of det and perm.