Algebra and Computation (2019-I)
The course would be structured similar to the previous offering of this course.
Wednesdays and Fridays 1400 — 1530 @ A 201
Course Calendar (.ical)
Lecture notes and resources
Lecture Notes (PDF): algComp_2017.pdf
(last updated 2019-04-02_0947)
Source files and the git repository available at [megh]/ramprasad/algComp_2017/) (Accessible only internally) .
Sage Examples: (html) (.ipynb)
Summary of Lectures
Part 1: Computational Group Theory
- Lecture 1 (Monday, 2019-01-28)
- Introduction to the course, basics of computational group theory, group actions, relevance to graph isomorphism and puzzles (15 puzzles, Rubik’s cube (2x2x2 and 3x3x3), Top Spin)
- Lecture 2 (Wednesday, 2019-01-30)
- Kernels, normal subgroups, cosets, stabilizers, the Orbit-Stabilizer Theorem, application to Cauchy’s theorem. Algorithms for orbit and transversals, Schreier’s lemma and computing stabilizers
- Lecture 3 (Friday, 2019-02-01)
- Schreier-Sims algorithm for membership testing in permutation groups, algorithm to compute the order of a group, testing normal etc. How commutative can a non-commutative group be?
- Lecture 4 (Wednesday, 2019-02-06)
- Discovering a solution to puzzles such as Rubik’s cube, TopSpin etc. via conjugates and commutators
- Lecture 5 (Friday, 2019-02-08)
- Computing commutator subgroups, normal closures, testing solvability of a group, testing subnormality, set-stabilizers and group intersections.
- Lecture 6 (Tuesday, 2019-02-12)
- More on set-stabilizers and group intersections. “Nice” tower of subgroups, and applications to cases of group intersection etc.
- Lecture 7 (Friday, 2019-02-15)
- Graph isomorphism of graphs with bounded colour multiplicity. General divide-and-conquer techniques in computational group theory, blocks and primitivity.
- Lecture 8 (Tuesday, 2019-02-19)
- Computing blocks, block systems and block kernels.
- Lecture 9 (Friday, 2019-02-22)
- Structure of p-groups, and conditions for primitivity. Introduction to divide and conquer for the colourStab problem
- Lecture 10 (Wednesday, 2019-02-27)
- Structure of Aute of a degree 3 graph, and solving isomorphism for trivalent graphs
- Lecture 11 (Thursday, 2019-02-28)
- Graph isomorphism for degree-3 graphs, colour refinements and isomorphism for trees, introduction to the Weisfeiler-Lehman process
- Lecture 12 (Wednesday, 2019-03-06)
- Lower bound of Cai-Furer-Immerman
-
- [Cai-Furer-Immerman] “An Optimal Lower Bound on the Number of Variables for Graph Identification” (Combinatorica)
- Lecture 13 (Friday, 2019-03-08)
- (continued) Lower bound of Cai-Furer-Immerman
-
- [Cai-Furer-Immerman]: “An Optimal Lower Bound on the Number of Variables for Graph Identification” (Combinatorica)
- Lecture 14 (Wednesday, 2019-03-13)
- An O(n) time algorithm for isomorphism testing of abelian groups of size n
-
- [Kavitha]: “Linear time algorithms for Abelian group isomorphism and related problems”, JCSS
- Lecture 15 (Friday, 2019-03-15)
- Ask-Me-Anything lecture for Part 1 of the course
Midsem (Wednesday, 2019-03-20)
Part 2: Integers and polynomials
- Lecture 16 (Wednesday, 2019-04-03)
- introducing rings, ideals, fractions and fields
- Lecture 17 (Friday, 2019-04-05)
- Construction of finite fields, gcd algorithm, Euclidian domains, UFDs etc. Sketch of FFT
- Lecture 18 (Wednesday, 2019-04-10)
- Analysis of FFT, polynomial multiplication in O(n log n) ring operations, polynomial division
- Lecture 19 (Friday, 2019-04-19)
- Cantor-Zassenhaus and Berlekam’s algorithms for factorising univariate polynomials over finite fields
- Lecture 20 (Wednesady, 2019-04-24)
- Towards factorising bivariate polynomials over finite fields: Hensel lifting and Resultants
- Lecture 21 (Friday, 2019-04-26)
- Factorising bivariate polynomials over finite fields
- Lecture 22 (Monday, 2019-04-29)
- Factorisation of polynomials over rationals: reducing to a question about approximating shortest vectors in a lattice.
- Lecture 23 (Wednesday, 2019-05-01)
- The Lenstra-Lenstra-Lovasz algorithm for computing a good approximation of the shortest vector in a lattice
- Lecture 24 (Friday, 2019-05-03)
- Integer factorisation: algorithms and heuristics. Pollard’s rho method, Pollard-Strassen method, and introduction to smooth numbers
- Lecture 25 (Wednesday: 2015-05-08)
- Dixon’s algorithm, and the quadratic sieve
- Lecture 26 (Friday: 2015-05-10)
- Algorithms for the discrete log problem (Pollard’s rho for discrete log, and index calculus methods)