A course involving various topics in TCS with an algebraic flavor.
Here is the complete syllabus:
- The extended Euclidean algorithm, exponentiation by repeated squaring, a polynomial algorithm for SAT.
- Different computation models (transdichotomous, bit complexity, arithmetic complexity), Karatsuba’s integer multiplication algorithm.
- Strassen’s matrix multiplication algorithm, tensors and tensor rank.
- Tensor rank and the exponent of matrix multiplication.
- Tensor rotation, tensor product, direct sum of tensors, border rank.
- Asymptotic sum inequality, the Coppersmith–Winograd algorithm (briefly).
- Discrete Fourier transform.
- Fast Fourier transform.
- Schönhage–Strassen integer multiplication algorithm.
- Primality tests: Fermat, Solovay–Strassen, Miller–Rabin (without proof), AKS (only briefly mentioned).
- Integer factorization algorithms: Pollard’s rho, Pollard’s $p-1$, the elliptic curve method.
- Guest talk by the teaching assistant (Tamer Mour) on factorization using elliptic curves.
- More integer factorization algorithms: quadratic sieve, number field sieve (briefly).
I prepared lecture notes for some of these subjects:
More details are available on webcourse.
