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)

Problem sets

  • Problem Set 1: [PDF] (Deadline: 2019-02-10)
  • Problem Set 2: [PDF] (Deadline: 2019-03-03)
  • Midsem: [PDF]
  • Problem Set 3: [PDF] (Deadline: 2019-05-12)

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)

References