Topics for CPSC 536J for Spring 2019 

Linear algebra can be used to determine unapparent global information from
local data.  The main goal of the course is to introduce some tools in
linear algebra used in algorithms and complexity theory, and to describe the
connection of these tools to open problems there and to other areas in
computer science.

I will assume some exposure to linear algebra and sufficient "mathematical
maturity."  When we discuss Betti numbers, it will be helpful to have seen
some point-set topology.

Most likely I will cover the basic ideas behind toolsets (1) and (2), and
then choose some of the topics/applications in both.  Part of my choice of
topics will depend on the interests of the students.  I may add other
topics.

--------------------------------------------------

(Toolset 1) Eigenvalues and eigenfunctions of matrices, for matrices
modeling graphs, networks, and Markov chains.

Sample Topics and Applications: Expanders and applications such as
connection networks, Expander Codes (Sipser-Spielman), randomness boosting,
etc.).  Mixing in Markov chains and applications.  SVD and low rank
approximation.  Relative expansion and Markov chain refinement.  Detection
of cliques and other hidden features of large networks.

Possible Brief Discussion of: the Moore Bound, Unique Games Conjecture
over expanders.  Approximating the permanent.  Shannon's algorithm,
constrained data, regular languages.  Zeta functions.  Sheaf theory on
graphs and cohomology.  Fibre products, relativization, Galois theory.

----------

(Toolset 2) Simplicial complexes and Betti numbers.  Computational topology
and Hodge theory.

Sample Topics and Applications: Persistant Homology.  Ben-Or's remark
regarding complexity (e.g., P versus NP) (Remark 8.1 of Lower Bounds For
Algebraic Computation Trees, ACM STOC 1983).  Higher dimensional expanders.
Nash equilibrium (via Kakutani's and Brouwer's fixed point theorems).

----------

(Other toolsets 3) Other possible brief discussions: Permanent versus
Determinant; the Mulmuley-Sohoni approach; connection to matrix
multiplication.  Solution to LP's with specified zeros, colourful Helly's
theorem.