Algebra and Computation



  • 2017 Spring/Summer (Jan - May)

Intended number of lectures: ~25 (1.5 hours each)
The course would be divided into three broad parts. 
Part 1: Group theoretic algorithms
Review of basic group theory, permutation groups. Graph isomorphism and the graph automorphism problem. Membership in permutation groups, and polynomial time testing of various standard group properties (subgroup membership, finding the smallest normal subgroup containing H, checking if subgroup is normal etc.).
Graph isomorphism of bounded degree graphs in polynomial time. 
Graph isomorphism for general graphs in n^{O(sqrt{n})} time. 

Part 2: Polynomial factorisation
Root finding over finite fields, Berlekamp’s univariate polynomial factorisation over finite fields.
Hensel lifting, bivariate factorisation over finite fields, 
Lenstra-Lenstra-Lovasz’s shortest vector approximation algorithm and applying that for factoring univariate polynomials over Q
Hilbert’s irreducibility theorem and Kaltofen’s blackbox factorisation. 
References: relevant lectures from

Part 3: Very basic algebraic geometry from a computational perspective
Ideals, varieties, Grobner basis, ideal membership, 
Hilbert Nullstellensatz, basic elimination theory
References: relevant lectures from
[CLO]: “Ideals, varieties and algorithms” by Cox, Little and O’Shea 

- Each student would be required to scribe at least one lecture. You get additional score for correcting typos of other lectures etc. The scribing would count towards 10% of the final evaluation. 
- There would be about 3-4 assignments and these would carry 45% towards the final evaluation. 
- There would be an end-semester exam (most likely a take-home exam) the would carry 45% towards the final evaluation.