Lectures

Algebra and Computation (January-May 2012)

School of Technology and Computer Science, TIFR, Mumbai.

Instructor: Ratnik Gandhi

Evaluation:    Assignments (20%)
                    Paper Presentation(30%)
                    Exam(50%)

 
Lecture
No.
 
Date
 
Topics/ Participating Speaker
 
Notes
 
Hrs

 1

 Feb 1, 2012

 Group, Dihedral group, Subgroup, Order of a group, Generator, abelian group, Rings, Administrative details

Her

 

 2

 Feb 7, 2012

Normal subgroups, Group homomorphism

Her

3

 3

 Feb 8, 2012

 Integral Domain, Division Rings, Fields, Finite Fields, Characteristic, Ring homomorphism

Nithin: Rainbow Connectivity- Introduction

 

 4

 Feb 14, 2012

 Ideals, Quotient Rings, Integral Domain, Maximal Ideals, Euclidean Ring, PID

Her

6

 5

Feb 15, 2012

Nithin: Rainbow Connectivity via Polynomials

 Ref

 6

 Feb 21, 2012

UFT, Polynomial Rings, Division Algorithm

Her

9

 7

Feb 22, 2012

Ratnik: Rainbow Connectivity via Ideal Membership

 Ref

10

 

 Feb 24, 2012

 Assignment 1

 Due March 4, 2012

 

 8

Feb 28, 2012

 UFD, Irreducibility Criterion, Polynomial Ring over commutative rings, Algebraic Extensions of a field

Her

 12 

 9

 Feb 29, 2012

Rakesh: Evasiveness of Graph Properties - 1

Ref 1, Ref 2

13

 10

 March 6, 2012

 Degree of an algebraic element, minimal polynomial, roots of a polynomial, splitting fields

Her

 15 

 11

 March 7, 2012

 Rakesh: Evasiveness of Graph Properties - 2

Ref 1, Ref 2 

 16 

12 

March 13, 2012 

Affine Variety, Ideal of a variety, unions and intersection of varieties 

CLO

18

13

March 14, 2012

Rahul: Space time codes as an exaple of division Ring

Ref

19

 14

March 20, 2012 

Monomial orders, Multivariate Division Algorithm, Monomial ideals and Dickson's Lemma

CLO

 21 

 15

March 21, 2012 

Rakesh: Evasiveness of Graph Properties - 3
 

Ref 1, Ref 2 

22

 16

March 27, 2012

Hilbert basis theorem, Groebner basis, Properties of Groebner basis

 CLO

24 

17

 March 28, 2012

Ratnik: Characterization of Nash equilibria as solutions to system of polynomial equations

Ref

25 

 18

April 3, 2012

Buchberger's Algorithm, Ideal membership, Polynomial System solving

 CLO

 27

 19

 April 4, 2012

Ratnik: Lower bound on computing a Pure Strategy Nash equilibrium

Ref

 28

20

 April 17, 2012

Distinct Degree Factorization 

 Gathen

 30

 21

April 18, 2012 

 Girish:  Harmonic Analysis over Finite Abelian Groups -1   

Ref 1, Ref 2

 31

 22

April 24, 2012 

 Equal degree Factorization

Gathen

 33

23

April 25, 2012 

Square Free factorization     

Gathen

 35 

 24

May 1, 2012 

 Hansel Lifting -1

Arvind/ Sudan

 37 

 25

May 2, 2012 

Girish:  Harmonic Analysis over Finite Abelian Groups -2 

Ref 1, Ref 2 

 39

 26

May 8, 2012 

 Hansel Lifting -2

Arvind/ Sudan

 41

 27

 May 9, 2012

 Nithin: Kakeya Sets  

Ref

 42

 28

 May 15, 2012

Factorization using short vectors

Not Covered

 44


29

May 30, 2012

Exam




References

  1.     Joachim von zur Gathen and Jürgen Gerhard: Modern Computer Algebra [Gathen]
  2.     Topics in Algebra. I N Herstein.[Her]
  3.     Concrete Abstract Algebra. Niels Lauritzen.
  4.     V Arvind: http://www.imsc.res.in/~arvind/notes.pdf [Arvind]
  5.     Madhu Sudan http://people.csail.mit.edu/madhu/FT98/course.html [Sudan]
  6.     Computational Number Theory  http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt
  7.     Algorithms for Computer Algebra. Keith O. Geddes, Stephen R. Czapor, George Labahn
  8.     Geometric algorithms and combinatorial optimization. Martin Grötschel, László Lovász, A. Schrijver
  9.     Ideals, Varieties and Algorithms. Cox, Little, O'Shea. Springer. [CLO]


Feedback: algebra.computation @ gmail.com































 

Comments