Algebra and Computation (2019I)
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 20190402_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: 20190210)
 Problem Set 2: [PDF] (Deadline: 20190303)
 Midsem: [PDF]
 Problem Set 3: [PDF] (Deadline: 20190512)
Summary of Lectures
Part 1: Computational Group Theory
 Lecture 1 (Monday, 20190128)
 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, 20190130)
 Kernels, normal subgroups, cosets, stabilizers, the OrbitStabilizer Theorem, application to Cauchy’s theorem. Algorithms for orbit and transversals, Schreier’s lemma and computing stabilizers
 Lecture 3 (Friday, 20190201)
 SchreierSims algorithm for membership testing in permutation groups, algorithm to compute the order of a group, testing normal etc. How commutative can a noncommutative group be?
 Lecture 4 (Wednesday, 20190206)
 Discovering a solution to puzzles such as Rubik’s cube, TopSpin etc. via conjugates and commutators
 Lecture 5 (Friday, 20190208)
 Computing commutator subgroups, normal closures, testing solvability of a group, testing subnormality, setstabilizers and group intersections.
 Lecture 6 (Tuesday, 20190212)
 More on setstabilizers and group intersections. “Nice” tower of subgroups, and applications to cases of group intersection etc.
 Lecture 7 (Friday, 20190215)
 Graph isomorphism of graphs with bounded colour multiplicity. General divideandconquer techniques in computational group theory, blocks and primitivity.
 Lecture 8 (Tuesday, 20190219)
 Computing blocks, block systems and block kernels.
 Lecture 9 (Friday, 20190222)
 Structure of pgroups, and conditions for primitivity. Introduction to divide and conquer for the colourStab problem
 Lecture 10 (Wednesday, 20190227)
 Structure of Aut_{e} of a degree 3 graph, and solving isomorphism for trivalent graphs
 Lecture 11 (Thursday, 20190228)
 Graph isomorphism for degree3 graphs, colour refinements and isomorphism for trees, introduction to the WeisfeilerLehman process
 Lecture 12 (Wednesday, 20190306)
 Lower bound of CaiFurerImmerman

 [CaiFurerImmerman] “An Optimal Lower Bound on the Number of Variables for Graph Identification” (Combinatorica)
 Lecture 13 (Friday, 20190308)
 (continued) Lower bound of CaiFurerImmerman

 [CaiFurerImmerman]: “An Optimal Lower Bound on the Number of Variables for Graph Identification” (Combinatorica)
 Lecture 14 (Wednesday, 20190313)
 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, 20190315)
 AskMeAnything lecture for Part 1 of the course
Midsem (Wednesday, 20190320)
Part 2: Integers and polynomials
 Lecture 16 (Wednesday, 20190403)
 introducing rings, ideals, fractions and fields
 Lecture 17 (Friday, 20190405)
 Construction of finite fields, gcd algorithm, Euclidian domains, UFDs etc. Sketch of FFT
 Lecture 18 (Wednesday, 20190410)
 Analysis of FFT, polynomial multiplication in O(n log n) ring operations, polynomial division
 Lecture 19 (Friday, 20190419)
 CantorZassenhaus and Berlekam’s algorithms for factorising univariate polynomials over finite fields
 Lecture 20 (Wednesady, 20190424)
 Towards factorising bivariate polynomials over finite fields: Hensel lifting and Resultants
 Lecture 21 (Friday, 20190426)
 Factorising bivariate polynomials over finite fields
 Lecture 22 (Monday, 20190429)
 Factorisation of polynomials over rationals: reducing to a question about approximating shortest vectors in a lattice.
 Lecture 23 (Wednesday, 20190501)
 The LenstraLenstraLovasz algorithm for computing a good approximation of the shortest vector in a lattice
 Lecture 24 (Friday, 20190503)
 Integer factorisation: algorithms and heuristics. Pollard’s rho method, PollardStrassen method, and introduction to smooth numbers
 Lecture 25 (Wednesday: 20150508)
 Dixon’s algorithm, and the quadratic sieve
 Lecture 26 (Friday: 20150510)
 Algorithms for the discrete log problem (Pollard’s rho for discrete log, and index calculus methods)