For full functionality of this site it is necessary to enable JavaScript.
Here are the
instructions how to enable JavaScript in your web browser.

# 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.

Abstract

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.

Assessment

Grade will be based on: Class participation - .3, Homeworks - .35, Projects - .35.

References

[1] Garrett Birkhoff and Thomas C. Bartee, Modern Applied Algebra, 1970.

[2] Noga Alon, Combinatorial Nullstellensatz, available at www.tau.ac.il/ nogaa/PDFS/null2.pdf