 |
CPSC 536F Page, Spring 2022
This page concerns CPSC 536F, Winter 2021-22, Term 2.
This is a topics course in the theory of computation.
This page has the most up-to-date information on the course(s) and
supersedes any other document.
Materials below may have errors!
Errors will be corrected either here or in class.
If you are not attending my classes: use these materials at your
own risk!
| News |
March 24:
Newest homework problems:
Problem 13 of
Homework Set 1,
and Problems 1-8 of
Homework Set 2.
March 15:
Major revision of my
skeletal notes on graphs and eigenvalues
to include facts about covering maps and etale maps that we will use
to prove the Alon-Boppana theorem.
I have made some additional corrections
to Homework Set 1
pointed out by Philip.
March 8:
Corrections made to Homework 1; problems 2, 4-8, and 10-12 of
Homework Set 1
due on March 15.
I have started some
skeletal notes on graphs and eigenvalues.
Until Feb 15:
Problems 10-12 of
Feb 1:
Diversity news: February is Black History Month in Canada.
For example,
with your UBC CWL you can (free of charge) watch
I
Am Not Your Negro (James Baldwin, posthumously)
and participate in numerous
events at UBC.
Jan 28:
I have started formally writing up homework problems, some of which
are to be handed in; see below.
I will add to this set in the coming weeks.
Jan 7:
I'm currently gathering a list of useful references for our coverage
of formulas/circuits; see below. I believe all UBC students should be able to
access the articles from these links; if not, please let me know
(first try posting to Piazza).
Jan 4:
(At least) the first two weeks of classes will be taught remotely;
the Zoom links are available via
UBC's Canvas system.
|
|---|
|
In-Person and Remote Learning
|
Classes will be given in-person, except
when UBC requires
us to teach remotely.
As of Jan 4: (at least) the first two weeks of classes will be taught remotely.
Generally speaking, classes will not be recorded.
Board scans will be posted below.
Remote teaching will be given via
Zoom, the links will be available at
Canvas at UBC.
If you have any issues, please post to
our course
piazza page.
|
|---|
|
Possible Course Topics this Term |
UNDER CONSTRUCTION!!
This is a "topics course" in theoretical computer science.
This term I intend to cover topics from the areas below.
-
Complexity Theory (the first 1/3 to 1/2 of the course, including
diversions to the "probabilistic method" and Kirchhoff's theorem):
-
Boolean formula size and monotone Boolean formula size.
Monotone formulas for threshold functions and
Valiant's majority construction.
-
Complexity of Boolean and algebraic functions, in terms of
formulas and circuits, specifically their size and depth.
Spira's theorem (relating depth to formula size).
-
"P vs. NP" and polynomial size circuits.
-
This
elegant and readable 1983 article of
Berkowitz, Rackoff, Skyum, and Valiant on parallelizing
algebraic sequential
computation (really a culmination of
works of Strassen, Csanky, Hyfil, and others in the 1970's,
and of Valiant and Skyum in 1981: see below for more references)
shows that
any algebraic circuit of size C (size includes the input variables)
computing a polynomial
of degree d in its inputs can also be computed by O(C^3) processors
in time order log(C)log(d)
(and C^3 can be improved to C^alpha log(d) where alpha is the exponent
of matrix multiplication).
-
Valiant proves that the Permanent is (NP-hard and) #P-complete
(under reductions in the BOOLEAN model).
-
Valiant's article Completeness Classes in Algebra (STOC 1979)
proves that an ALGEBRAIC formula of size m can be computed by
an m' x m' determinant with m' of size order m
(the paper claims m' = m+2, but a subtle error makes the method
yield m' more like 2m + const).
-
The above work draws attention to the problem of the min circuit size
for the permanent, conjectured to be superpolynomial.
(P != NP does not imply a such superpolynomial lower bound--as far as
I know--since a depth (log n)^2 formula/circuit could have integers with
n^(log n) many bits or digits.)
Current work
regards the minimum formula size for the permanent.
-
Symmetries of determinant and of a (binary, complete) alternating +/x tree
of a given depth.
An alternate view and some variants on the
Mulmuley-Sohoni approach to permanent vs. determinant
(this view and variants are my own,
although likely some researchers have similar ideas).
-
Remarks about algebraic decision trees and Betti numbers in the early 1980's
found in this
1982 article by Steele and Yao, "Lower Bounds for Algebraic
Decision Trees
and this
1983 STOC abstract by Ben-Or, "Lower bounds for algebraic computation
trees",
based on the Dobkin-Lipton results that count connected components.
-
Razborov's superpolynomial lower bound
on the monotone circuit size for
for clique function
(STOC 1989
abstract):
here is
a nice 2009 article by Gowers on Razborov's work, based on the
Alon-Bopanna version of
Razborov's work.
-
Algorithmic applications of eigenvalues/vectors:
(mostly definitions, examples, and statements of theorems without proofs)
-
Definitions of graphs and directed graphs, adjacency matrices.
Laplacians on graphs.
-
Markov matrices as weighted digraphs.
-
Eigenvalues, expansion, and mixing times of Markov matrices.
-
Counting methods (a.k.a. the probabilistic method) to prove the
existence of expanders.
-
Cayley graphs in expanders and Markov matrices.
-
Zeta functions of graphs.
-
The Perron-Frobenius theorem. Shannon's algorithm for variable-length graphs.
-
Research Topics:
-
Coverings (lifts) of graphs: automorphisms and Galois theory of graphs.
New and old eigenvalues. Relative expanders.
-
Universal covers; the profinite universal cover.
-
Coverings over a fixed graph: associated vector bundles, Galois representations.
-
Sheaves on graphs: general setup, examples: vector bundles, pseudo-bundles.
-
Reduced Betti numbers and limits over graphs covers.
-
k-independence of vector spaces. 2-independence and sheaves on graphs with
two vertices. Genearlization to simple categories.
-
Information theory and "linear information theory."
|
|---|
|
Supplemental References and Handouts |
UNDER CONSTRUCTION!!
There is no reference for this course. Here we will list some
articles related to course material, to supplement class discussion
and the references
mentioned in the Course Topics above.
(Again, as in the Course Topics above, we will use only
some of these references and handouts.)
-
Formula and Circuit Complexity
I am currently adding some contents from my previous courses, Math 523,
and CPSC topics courses on complexity theory that should eventually appear
on my Course Materials webpage.
-
There is a rich literature on lower bounds
for Boolean formula size. For formula size using the gates NEG,AND,OR, the
best lower bound to date is roughly n^3 for an explicitly described
function, namely Andreev's function, given by
Hastad's 1998 paper on
the Subbotovskaya's shirkage exponent (of de Morgan formulas);
this is a good place to start;
Hastad's paper refers to
Khraphchenko's essentially tight order n^2 for parity over this
basis of functions (which is clearly order n if XOR gates are allowed).
Hence these papers are highly dependent on the gates one uses.
A recent summary of various results and approaches can be found in these
Lecture 3,
Circuit Complexity course notes of B. Rossman.
-
The connection between circuit complexity
and the problem P versus NP can be found in many sources, including the
CPSC 421/501 textbook by Sipser (in Chapter 9).
-
Every CS theoretician should also know the problems of
"The Exponent of Matrix Multiplication" and
"Permanent Versus Determinant:"
The algebraic model has some surprising foundations developed in the
1970's in the
interest of matrix multiplication (NOT algebraic complexity). These
results include
Strassen's 1973 paper on eliminating divisions in
algebraic computations (as well as, of course,
Strassen's algorithm (for matrix multiplication)).
Csanky shows that an n x n matrix A can be inverted in time
O(log n)^2 with poly(n) processors
(the time it takes to compute Trace(A),...,Trace(A^n), log_2(n) per matrix
multiplication, and then the time
to invert the Newton identities);
Hyafil generalizes this result--using ideas
from Strassen's paper above--to
parallelizing any computation of a degree d polynomial in n variables
with C "sequential steps" (i.e., a circuit of size C+n)
to an order log(C+n)log(d) depth
formula.
[ADD MORE ARTICLES HERE.]
-
More work on decision trees for algebraic computation trees includes:
this STOC 1992
abstract of Bjorner, Lovasz, and Yao, Linear decision trees:
volume estimates and topological bounds and
this FOCS 1994 abstract
of Ben-Or, "Algebraic computation trees in characteristic p>0",
which references work of Bjorner, Lovasz, and Yao.
-
In Math 523 in 2014 I used
these notes on formulas and circuits, and
these notes on the Mulmuley-Sohoni approach
(commonly called Geometric Complexity Theory, since it involves techniques
from algebraic geometry).
The following article, Section 6.1, summarizes our variants of the
Mulmuley-Sohoni approach to the problem "permanent vs. determinant"
The Cook-Levin
Theorem and how to solve and not to solve P versus NP,
(last revised December 8, 2021).
|
|---|
|
Boards Scans |
-
Formula/circuit depth/size complexity in the Boolean model and in the
algebraic model.
Board scans:
01_11.
Overview and policy. Definition of
Boolean formula size wrt NEG,AND,OR. Simple example.
01_13.
Boolean formula size, De Morgan formulas.
01_18 Bounds on number of formulas
of size s on n variables.
01_20 Bounds on number of formulas and
circuits
of size s on n variables. Method for finding s=s(n) with
(1) s log(n) ~ 2^n, (2) s log(s) ~ 2^n, and similarly.
01_25 Parity has O(n^2) De Morgan formula,
Subbotovskaya's shrinkage
exponent of 3/2.
01_27 Homework, plus
Andreev's function. Spira's lemma.
02_01 More on Andreev's function and the
union bound.
Monotone functions. Threshold functions, majority function.
There are at least 2^(n choose n/2) monotone functions.
Th_2 on n variables has O(n log n) size formulas (explicit constructions)
Th_3 on n variables has O(n log n) size formulas (probabilistic method).
02_03
More remarks on the probabilistic method and union bound.
Begin Valiant's monotone majority.
02_08 Finish Valiant's monotone
majority. Begin permanent.
02_10 Valiant's 4x4 permanent gadget,
and outline of Valiant's reduction of #3SAT to permanent of a matrix with
{-1,0,1,2,3} entries.
02_15 Finish Valiant's reduction from
#3SAT to computating a {-1,0,1,2,3} permanent.
-
Review of graphs, digraphs, and their adjacency and Laplacian matrices.
Markov matricies. Examples.
Board scans:
02_17 Definition of directed graphs, graphs,
d-regular graphs, start
eigenvalues of adjacency matrices.
03_01 Eigenvalues of d-regular graphs:
maximum principle and multiplicity of d and -d as eigenvalues;
review of spectral theorem for symmetric matrices; decomposition as
adjacency matrix of d-regular graph into (d/n) time all 1's matrix plus
an "error term". Eigenpairs of some Boolean hypercubes; cartesian
product.
03_03 Boolean hypercube as cartesion power
of the 1-dim hypercube; the hypercube as the matching graph of a
very simple bipartite graph; rough idea of approximate counting of
perfect matchings. Eigenpairs for cycles and circulant matrices;
eigenpairs for "grid graphs."
03_08 The usual statement of the
"expander mixing
lemma." Motivation for the mixing time. Bounding the mixing time
of Markov matrices obtained from regular graphs by using the
mixing lemma.
03_10 A diameter bound for regular graphs
in terms of the spectrum. Lower bounds on second eigenvalue and the
max-min principle. Idea of Alon-Boppana type bounds.
03_15 Lower bounds on r-th eigenvalue
in terms of r induced subgraphs of distance at least two from each other.
Largest eigenvalue of truncated d-regular tree.
03_17 Morphisms of digraphs/graphs
(i.e., digraph/graph homomorphisms), covering maps and etale maps of
digraphs and graphs, example of the hypercube covering map to the
Ehrenfest model.
03_22 Covering morphisms, Galois
morphisms, all 2-to-1 morphism are Galois, computation of covering
graph eigenvalues in terms of adjacency and signed adjacency matrix.
03_24 The 5-to-1 Galois covering
map from the
Petersen graph (which is also a Kneser graph)
to a graph with two vertices, and the 2-to-1 map Galois covering
of the latter graph to a graph with one vertex.
Computation of the Petersen graph eigenvalues using the 5-to-1
map and fifth roots of unity.
The 10-to-1 composition covering map is not Galois.
The walk lifting lemma for covering maps; its application to show
that for a k-to-1 covering map H to G, Aut_H(G) is of order at
most k.
03_29 The normal extension theorem.
-
More topics to appear:
Board scans:
SCANS TO GO HERE
|
|---|
| Homework and Grades |
Homework will be assigned during lectures and organized
into two or three sets, to be collected at regular interval(s)
during the term.
Homework so far:
Until Jan 27:
Problems 2 and 4-8 of
Homework Set 1.
Until Feb 15:
Problems 10-12 of
Homework Set 1.
Until March 24:
Problem 13 of
Homework Set 1,
and Problems 1-8 of
Homework Set 2.
In my topics courses, grades have the following meaning (this is based
on UBC Math guidelines):
-
95% or higher (A+):
student is strongly encouraged to pursue research in the
area; the instructor will write a very strong letter of recommendation for the
student.
-
90% or higher (A+):
the student is encouraged to pursue research in the area
or a related one; the instructor will write an enthusiastic letter of
recommendation for the student.
-
85% to 89% (A):
the student will be able to use some of the course material
in another field of research; research in the area is not encouraged without
significantly more background and study.
-
80% to 84% (A-):
the student has fulfilled department expectations of the
graduate student.
-
79% or below (B+ or below):
the student has not fulfilled department
expectations of the graduate student.
|
|---|
|
Piazza |
There will be an online discussion of this course on
www.piazza.com; use
this link
to sign up.
Please post all questions related to the course material
to our piazza site.
|
|---|
| Diversity and Equity |
UBC is trying in earnest to
encourage
diversity and
alleviate biases and inequities
to which some members of its community are subjected;
this includes, for example, UBC's
Indian Residential School History and Dialogue Centre,
privileged to work with
the Musqueam First Nation
(recently, as of mid-August,
investigating St. Paul's Indian Residential School site
[Content warning: This post discusses Indian residential schools.]);
this also includes
the Computer Science Department's various programs described on its
Diversity in CS
webpage.
I try to act reasonably free of bias; for example,
I do not view
sexual orientation or gender as
set in stone from birth or as classified by some fixed, finite set of
choices; I try
to use language accordingly.
I will undoubtedly
goof upon occasion, and I welcome feedback on these and related matters.
|
|---|
|
Relevant Dates
|
(Our) Class Starts: Tuesday, Jan 11.
Drop/Withdrawl: Jan 21.
Family Day + Feb Break: Feb 21-25.
Last day of (our) class: Thursday, April 7.
All homework, etc. is due on the last day of classes, Friday, April 8.
|
|---|
|