Show The Graduate Center Menu

Theoretical Computer Science


Theoretical Computer Science: Complexity Theory,
Group Theory, Finite Fields, Linear Algebra
Instructor: Professor Leonid Gurvits (The City College of New York), spring semester, 2015.
The main theme of the course will be an algebraic(mainly linear-algebraic) approach to various problems, ranging from finite automatons to machine learning, including several
Putnam problems. The following topics will be covered:
• Finite Commutative Fields: characterizations, constructions, applications (Reed-Solomon codes, De Bruijn sequences... will follow the exposition from [1] )
• Linear and Multilinear Algebra approach to Group Theory, Combinatorics, Geometry(Several Applications, starting with the VC-Dimension, the odd-town and odd distances (Putnam) problems... [2] will be heavily used).
• Perron-Frobenious Theorem, Markov Chains and Finite Automatons.
• Basics of the graph spectra theory, graph lifts and matching polynomials.
• Transitive subgroups of permutations, Polya Theory.
• Positive Sefidefinite Matrices, Majorization, Elements of Quantum Information.
• Important Hardness Results: Quantum Entanglement, Robust/Switching Stability.
• Quaternions and computer vision.
The participants will learn really cool proof tricks/methods and, as a bonus, will get familiar with some fundamental facts and theorems connecting the discrete and continuous worlds.
Grade will be based on: Class participation - .3, Homeworks - .35, Projects - .35.
[1] Garrett Birkhoff and Thomas C. Bartee, Modern Applied Algebra, 1970.
[2] Noga Alon, Combinatorial Nullstellensatz, available at nogaa/PDFS/null2.pdf