Outline of what I have covered so far, with sources, and presentation topics
-------------------------------------------------------------------------

Week 1. Organization, some important arithmetical functions: 
multiplication (n^2 by standard method, but can be done in nearly nlogn via FFT),
determinant, permanent, matrix multiplication, the FFT (Fast Fourier Transform) itself,
linear programming.  What I call "Week 2" started in the second lecture.

Sources: A typical Algos book; Cormen-Leiserson-Rivest(-Stein) has FFT and Strassen's matrix mult.  


Weeks 1-2. The arithmetic circuit model.  Different fields and rings: C,R,Q are fields, as is Z_p
when p is prime, but Z_m for m composite is "just a ring".  Sometimes all you need are 0 and 1
and the rest of the ring-or-field doesn't matter.  Or you might need -1 to be different from +1.
Equation solving.  Using equations over "AnyRing" to model the correct operation of a NAND gate.
Counting gates versus counting wires.

Sources: The Shpilka-Yehudayoff (SY) notes given out describe model tersely in sections 1.1--1.3.
Conversion of NAND gate to equations is not literally in any source, but you could "work it out" from
your notes: w = NAND(u,v) holds if and only if (w + u - wu)(w + v - wv)(1 - uvw) - 1 = 0.
Using the fact that when u,v,w are in {0,1}, u^2 = u etc., this multiplies out to give
w - uvw  + wv - uvw - wv + uvw + uw - uvw + uv - uvw - uvw + uvw - uw + uvw - uvw + uvw + uvw - uvw - 1 = 0.
Magically most of this cancels, so going beyond what I did in lecture, this gives:
w = NAND(u,v) <==> w + uv - 2uvw - 1 = 0.  (Please work out that this is correct...)  
New source: Madhu Sudan lecture notes http://people.csail.mit.edu/madhu/ST12/, lecture 18:
http://people.csail.mit.edu/madhu/ST12/scribe/lect18.pdf


Weeks 2-3: The Boolean complexity model.  Boolean circuits.  Complexity classes defined with
reference to different problems about solving equations.  /Uniform/ polynomial-size circuits C
as a definition of P.  Given x, whether there exists a y such that C(xy) = 1 as defining NP.
Truth tables and the Boolean satisfiability problem (SAT, 3SAT).  The Cook-Levin theorem that
SAT is NP-complete.  Connected with Week 2, this shows that whether equations have a solution 
with 0-1 arguments is likewise NP-complete.  (To reprise the details based on the above, for an 
entire circuit C(x,y) of NAND gates, take the product of (w + uv - 2uvw) over all gates g /and/
over all wires out of g, multiply by what I called "w_0" for the output wire, multiply by terms
x_i or (1 - x_i) according to whether a concrete binary string x you are substituting has bit
x_i = 1 or x_i = 0, and finally append " - 1 = 0" to make an equation E.  Then E has a 0-1
solution if and only there is a y such that C(x,y) = 1, which is if-and-only-if x belongs to
the language L in NP that we started with, for which C served as the "check y" predicate.
Unbounded fan-in gates: OK with arithmetical + and *, Boolean AND and OR, but beware NAND.

Sources: Chapters 1 (=27) and 2 (=28) of Allender-Loui-Regan chapters for CRC Handbook,
http://www.cse.buffalo.edu/~regan/papers/pdf/ALRch272up.pdf (mainly section 3)
http://www.cse.buffalo.edu/~regan/papers/pdf/ALRch282up.pdf (mainly just thru section 3)
Definition of classes via equations is included in section 2 of textbook I've been writing:
http://www.cse.buffalo.edu/~regan/cse705/BQPpolysim.pdf (Just section 2, rest is seminar option 9 below.)


Weeks 3-4: Comparing Boolean and arithmetic functions.  Different ways of representing Boolean
values in arithmetic: Should 0 = true, or 1 = true?  Should any non-0 value be allowed to give
true (as in C,C++), which I call "weak representation", or should we restrict so that values
outside {0,1} never happen ("strong representation")?  The key cost measures, in terms of n:
S(n) = min. size of arithmetical circuit representing f  (Could be better to name it AC(n).)
L(n) = min size of formula representing f
s(n) = min size of formula when multiplied out as a Sum-Of-Products.
d(n) = min degree of a representation, where it's often ambiguous whether the representation
is a formula or circuit, and whether the Formal Degree (before cancellation) or Semantic Degree
(after cancelling terms) is meant.  I also defined a measure s'(n) between s(n) and L(n) in
which the formula is written as a sum of "schematic terms", which are products of x_i and (1 - x_i).
Also defined the hierarchy:
Sigma = Sum, with coefficients and constants allowed, = affine linear functions.
Pi = Product.  A monomial is a product of variables, possibly powered; the coefficient makes a /term/.
Sigma-Pi = sum-of-products = sum-of-terms.
Pi-Sigma = product of affine linear factors = "completely split/factored form".
Sigma-Pi-Sigma = sum of products of factors.  [The "Chasm" papers show that proving any sub-exponential 
lower bound on S(n) or L(n) for Sigma-Pi-Sigma is equivalent to general case; this makes
higher Sigma-Pi-Sigma-Pi etc. levels now less important.]

Sources: SY notes, chapter 1, plus my own survey on polynomials in complexity theory
http://www.cse.buffalo.edu/~regan/papers/pdf/Polynomials.pdf
but *only* a few early pages (delving further into its references is seminar option 5 below).


Weeks 4--5: Partial derivatives---only make sense over C, R, or Q?  The Chain Rule.
The "Derivative Lemma": compute all n partials with only a factor-of-5 blowup in size.
Algebraic solution sets ("varieties"), irreducibility.  Concept of "Geometric Degree". 
The mapping-Jacobian (y_1 - df/dx_1, ..., y_n - df/dx_n) of f(x_1,...,x_n) is irreducible in C^{2n}.
Statement of Strassen's theorem: S(n) >= (1/5)\log_2(gdeg(MapJac f)).  (Did not sketch proof.)  Example 
f(x_1,...,x_n) = x_1^n + ... + x_n^n has gdeg at least (n-1)^n, so S_f(n) >= (1/5)n*log_2(n-1).
This is basically the only general kind of super-linear circuit size lower bound in complexity
theory known today, anywhere.  Why it doesn't apply to Boolean circuits, for which 5n is the best
general size lower bound known for any function or language in either NP or in E (= 2^{O(n)} time).
(In fact, not for any language in their combo E^{NP}, which does allow exponential-sized queries.)
The incredible ignorance of computational power that this represents.  A "Boolean Derivative Lemma"
for some notion of deriving a Boolean function f w.r. to a variable x_i would help, such as
D(f,i)(x) = f(x_1,...,x_{i-1},0,x_{i+1,...,x_n) XOR f(x_1,...,x_{i-1},1,x_{i+1,...,x_n).
But none is known, despite attempts by some smart people...possible seminar presentation topic 15.
Valiant's classes VP and VNP, analogous to P and NP.

Sources: SY notes, sections 1.2 and 2.3; also see my blog article "Projections Can Be Tricky"
http://rjlipton.wordpress.com/2010/08/19/projections-can-be-tricky/
New source: Madhu Sudan lecture 19: http://people.csail.mit.edu/madhu/ST12/scribe/lect19.pdf


Week 6, part: Homogenization, from SY notes, section 2.2; maybe also universality, section 2.1 and
a paper which came from seminar in 2004, http://www.cse.buffalo.edu/~regan/papers/pdf/LiRe05IPL.pdf


Some Possible Seminar Presentation Topics
-----------------------------------------

The "Capstone Objective" I have in mind is to cover the "Chasm" papers near the end of term, which would be
appropriate for someone considering to do a PhD in theory or a related subfield.  Especially the early topics
can build toward this, though after the first five they are basically independent.  Topics after "Chasm" are
speculative.  Links to "Chasm" papers are at http://rjlipton.wordpress.com/2013/12/30/the-winner-is/

1. The FFT and Fast Polynomial and Integer Multiplication.  [CLRS book is enough, also Sudan lecture 4]
2. Strassen's Matrix Multiplication Algorithm, and Possible Improvements.  [CLRS book, Kleinberg talk]
3. Primes in P (including relevant facts from number theory)   [digests of Agrawal-Kayal-Saxena paper]
4. The Degree/Depth Reduction Theorem [SY notes, section 2.4; VSBR paper itself optional] 
5. Representing Boolean Functions -- more results   [papers cited in my survey: BBR, BaTa...]
6. Polynomial Equations and Ideals, Groebner Basis Algorithm [Cox-Little-O'Shea book; also Sudan lectures
   15--17; combined with next item this can have 2 teams]
7. "Singular" Groebner-Solving Software, attack some algebraic lower-bound problems.  We have it installed;     
   on "metallica", just type "Singular" at UNIX prompt.  Manual online at http://www.singular.uni-kl.de/   
   For some inspiration vis-a-vis SAT solving, see http://rjlipton.wordpress.com/2014/02/28/practically-pnp/
8. VNP-complete Problems, more on VNP vs. VP [can use later parts of SY notes, linked from Sudan's ST12 page].
9. Polynomial Factorization [Sudan's notes, lectures 7 and 8]
10. Quantum Circuit Simulations [rest of my chapter http://www.cse.buffalo.edu/~regan/cse705/BQPpolysim.pdf]
11. Quantum Fourier Transform and its Algebraic Aspects.
12. The "Chasm" Papers and Lower Bounds.  [Click on "their" and "work" in post
    http://rjlipton.wordpress.com/2013/12/30/the-winner-is/ ]
13. Arithmetical Complexity With Restricted Cancellations [ongoing research, builds on Groebner bases]
14. Arithmetical Complexity With Restricted Circuits [papers by my PhD graduate Maurice Jansen]
15. The Boolean Derivative "Disease" ---can segue to the "Junta Problem".
16. Other topics I've mentioned in seminar?
17. Any relevant topic that strikes your interest...