CS6842 - Algorithmic Algebra

Meetings  

• Theme 1 : Introduction - 5 meetings

  • Meeting 01 : Tue, Aug 02, 08:00 am-08:50 am

  Administrative announcements. Graph isomorphism problem. Relation to computation of the automorphism group of a graph.

  References	NA.
  Exercises
  Reading

  Administrative announcements. Graph isomorphism problem. Relation to computation of the automorphism group of a graph.
  

  References:

  NA.

  • Meeting 02 : Wed, Aug 03, 06:00 am-06:00 am

  Agrawal Biswas primalitytest via identity testing.

  References	<a href="http://www.cse.iitk.ac.in/users/manindra/algebra/identity.pdf"> Article </a> by Agrawal-Biswas, Lemma 3.1
  Exercises
  Reading

  Agrawal Biswas primalitytest via identity testing.
  

  References:

  Article by Agrawal-Biswas, Lemma 3.1

  • Meeting 03 : Fri, Aug 05, 11:00 am-11:50 am

  Introduction to Groups. Definition. Lagrange's theorem.

  References
  Exercises
  Reading

  Introduction to Groups. Definition. Lagrange's theorem.
  

  References:

  None

  • Meeting 04 : Mon, Aug 08, 09:00 am-09:50 am

  Cosets. Normal Subgroup. Homomorphisms.

  References
  Exercises
  Reading

  Cosets. Normal Subgroup. Homomorphisms.
  

  References:

  None

  • Meeting 05 : Tue, Aug 09, 08:00 am-08:50 am

  Homomorphisms, Kernel and Image. First isomorphism Theorem. Symmetric group. Cycle decomposition. Permutation groups. Generators.

  References
  Exercises
  Reading

  Homomorphisms, Kernel and Image. First isomorphism Theorem. Symmetric group. Cycle decomposition. Permutation groups. Generators.
  

  References:

  None

• Theme 2 : Algorithms for groups - 15 meetings

  • Meeting 06 : Wed, Aug 10, 12:00 pm-01:00 pm

  Homomorphisms. Kernel and Image. Isomorphism Theorem. Symmetric group. Cycle decomposition. Generating set of a group. every Permutation group G has a generating set with at most log |G| elements.

  References
  Exercises
  Reading

  Homomorphisms. Kernel and Image. Isomorphism Theorem. Symmetric group. Cycle decomposition. Generating set of a group. every Permutation group G has a generating set with at most log |G| elements.
  

  References:

  None

  • Meeting 07 : Fri, Aug 12, 11:00 am-11:50 am

  Graph Automorpsim vs Graph Isomorphism. Colored graph isomorphism.

  References
  Exercises
  Reading

  Graph Automorpsim vs Graph Isomorphism. Colored graph isomorphism.
  

  References:

  None

  • Meeting 08 : Tue, Aug 16, 08:00 am-08:50 am

  Graph Rigidity to Graph isomorphism. Colored GI. Orbit and stabilizers.

  References	<a href="http://www.tcs.tifr.res.in/~ramprasad/lecturenotes/algcomp.php"> Notes </a> by V. Arvind.
  Exercises
  Reading

  Graph Rigidity to Graph isomorphism. Colored GI. Orbit and stabilizers.
  

  References:

  Notes by V. Arvind.

  • Meeting 09 : Wed, Aug 17, 06:00 am-06:00 am

  Reduction from Graph Automorphism to GI. Sylow's theorem. Proof.

  References	[Arv]
  Exercises
  Reading

  Reduction from Graph Automorphism to GI. Sylow's theorem. Proof.
  

  References:

  [Arv]

  • Meeting 10 : Thu, Aug 18, 09:00 am-09:50 am

  Sylow theorem. Computation of orbit. transitive groups. Blocks. Decomposition of transitive groups.

  References	[Arv]. Also see Herstein's Topics in Algebra.
  Exercises
  Reading

  Sylow theorem. Computation of orbit. transitive groups. Blocks. Decomposition of transitive groups.
  

  References:

  [Arv]. Also see Herstein's Topics in Algebra.

  • Meeting 11 : Fri, Aug 19, 11:00 am-11:50 am

  Blocks. Primitive groups. A characterization of primitive groups.

  References	[Arv]
  Exercises
  Reading

  Blocks. Primitive groups. A characterization of primitive groups.
  

  References:

  [Arv]

  • Meeting 12 : Mon, Aug 22, 09:00 am-09:50 am

  Characterization of primitive transitive groups.

  References	[Arv]
  Exercises
  Reading

  Characterization of primitive transitive groups.
  

  References:

  [Arv]

  • Meeting 13 : Tue, Aug 23, 08:00 am-08:50 am

  Algorithm for computing a block. Group membership via order computation. Outline. Schreir's Lemma.

  References	[Arv]. The proof of Schreir's lemma presented in the class (from [Arv]) is incomplete. For a complete proof of Schreir's Lemma, see Lemma 4.2.1 in [seress]. The generator given there is different from the one done in the class though.
  Exercises
  Reading

  Algorithm for computing a block. Group membership via order computation. Outline. Schreir's Lemma.
  

  References:

  [Arv]. The proof of Schreir's lemma presented in the class (from [Arv]) is incomplete. For a complete proof of Schreir's Lemma, see Lemma 4.2.1 in [seress]. The generator given there is different from the one done in the class though.

  • Meeting 14 : Wed, Aug 24, 06:00 am-06:00 am

  Group membership: complete algorithm. Related problems: Group intersection, Set Stabilizer.

  References	[Arv].
  Exercises
  Reading

  Group membership: complete algorithm. Related problems: Group intersection, Set Stabilizer.
  

  References:

  [Arv].

  • Meeting 15 : Fri, Aug 26, 11:00 am-11:50 am

  Algorithm for GI on special classes of graphs. Bounded valence GI.

  References	[Arv]
  Exercises
  Reading

  Algorithm for GI on special classes of graphs. Bounded valence GI.
  

  References:

  [Arv]

  • Meeting 16 : Mon, Aug 29, 09:00 am-09:50 am

  Bounded valence GI (contd)

  References	[Arv]
  Exercises
  Reading

  Bounded valence GI (contd)
  

  References:

  [Arv]

  • Meeting 17 : Tue, Aug 30, 08:00 am-08:50 am

  Bounded valence GI(contd). Set stabilizer problem for groups with small composition factors.

  References	[Arv]
  Exercises
  Reading

  Bounded valence GI(contd). Set stabilizer problem for groups with small composition factors.
  

  References:

  [Arv]

  • Meeting 18 : Wed, Aug 31, 06:00 am-06:00 am

  Set Stabilizer problem for groups with small composition factors (contd). Bounded color multiplicity GI.

  References	[Arv].
  Exercises
  Reading

  Set Stabilizer problem for groups with small composition factors (contd). Bounded color multiplicity GI.
  

  References:

  [Arv].

  • Meeting 19 : Fri, Sep 02, 11:00 am-11:50 am

  Bounded color multiplicity GI (contd). Application to general GI.

  References
  Exercises
  Reading

  Bounded color multiplicity GI (contd). Application to general GI.
  

  References:

  None

  • Meeting 20 : Tue, Sep 06, 08:00 am-08:50 am

  General - GI (contd)

  References
  Exercises
  Reading

  General - GI (contd)
  

  References:

  None

• Theme 3 : Algorithms for polynomials - 12 meetings

  • Meeting 21 : Wed, Sep 07, 06:00 am-06:00 am

  General - GI (completing the proof of color valence reduction). Introduction to rings and polynomials.

  References
  Exercises
  Reading

  General - GI (completing the proof of color valence reduction). Introduction to rings and polynomials.
  

  References:

  None

  • Meeting 22 : Fri, Sep 09, 11:00 am-11:50 am

  The polynomial ring. Homomorphism of rings. Kernel and Image. Definition of an ideal.

  References	Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's Algebra.
  Exercises
  Reading

  The polynomial ring. Homomorphism of rings. Kernel and Image. Definition of an ideal.
  

  References:

  Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's Algebra.

  • Meeting 23 : Mon, Sep 12, 12:00 pm-12:50 pm

  Examples of ideals of a polynomial ring and the ring of integers. Homomorphism of rings. Integral Domain. Principal Ideal domain. (Definition and examples only). Ideals and their geometry. Radical ideals of the polynomial ring K[x_1,...,x_n] are in 1 - 1 correspondence with subsets of K^n.

  References	Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"
  Exercises
  Reading	For more on principal ideal domains, see <a href="http://www.math.harvard.edu/~waffle/pids.pdf"> Noted </a> by Waffle.

  Examples of ideals of a polynomial ring and the ring of integers. Homomorphism of rings. Integral Domain. Principal Ideal domain. (Definition and examples only). Ideals and their geometry. Radical ideals of the polynomial ring K[x_1,...,x_n] are in 1 - 1 correspondence with subsets of K^n.
  

  References:	Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"
  Reading:	For more on principal ideal domains, see Noted by Waffle.

  • Meeting 24 : Wed, Sep 14, 06:00 am-06:00 am

  Generating set for ideals. Finitely generated ideals. Definition of Noetherian rings. Hilbert's basis theorem.

  References	Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"
  Exercises
  Reading

  Generating set for ideals. Finitely generated ideals. Definition of Noetherian rings. Hilbert's basis theorem.
  

  References:

  Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"

  • Meeting 25 : Fri, Sep 16, 11:00 am-11:50 am

  Proof of Hilbert's basis theorem.

  References	Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"
  Exercises
  Reading

  Proof of Hilbert's basis theorem.
  

  References:

  Any Book on algebra. E.g Artin's "Algebra" or Serge Lang's "Algebra"

  • Meeting 26 : Mon, Sep 19, 09:00 am-09:50 am

  Computational problems over polynomials: Factorization, Ideal Membership, Solving polynomial equation.

  References	For term ordering see [AL]
  Exercises
  Reading

  Computational problems over polynomials: Factorization, Ideal Membership, Solving polynomial equation.
  

  References:

  For term ordering see [AL]

  • Meeting 27 : Tue, Sep 20, 08:00 am-08:50 am

  Ideal membership: Uni-variate case. Need for well-ordering of terms. Definition of term ordering. Examples of term orderings.

  References	[Mishra] or [AL].
  Exercises	[AL] has a good set of examples and a large collection of exercises. Do for example 1.4.1, 1.4.3, 1.4.6, 1.4.8, 1.4.9 and 1.4.12.
  Reading

  Ideal membership: Uni-variate case. Need for well-ordering of terms. Definition of term ordering. Examples of term orderings.
  

  References:	[Mishra] or [AL].
  Exercises:	[AL] has a good set of examples and a large collection of exercises. Do for example 1.4.1, 1.4.3, 1.4.6, 1.4.8, 1.4.9 and 1.4.12.

  • Meeting 28 : Wed, Sep 21, 06:00 am-06:00 am

  Division algorithm for multivariate polynomials. non-uniqueness of the remainder. Initial ideal. Monomial ideals have a finite set of monomial generators.

  References	[Mishra], [AL]. <a href="http://cs.nyu.edu/yap/book/berlin/"> Book</a> by Chee Yap is also a good reference.
  Exercises
  Reading

  Division algorithm for multivariate polynomials. non-uniqueness of the remainder. Initial ideal. Monomial ideals have a finite set of monomial generators.
  

  References:

  [Mishra], [AL]. Book by Chee Yap is also a good reference.

  • Meeting 29 : Fri, Sep 23, 11:00 am-11:50 am

  Can the leading monomials of a generating set generate the initial ideal? Definition of Groebner basis. Equivalent conditions. Existence. S-polynomials.

  References
  Exercises
  Reading

  Can the leading monomials of a generating set generate the initial ideal? Definition of Groebner basis. Equivalent conditions. Existence. S-polynomials.
  

  References:

  None

  • Meeting 30 : Tue, Sep 27, 08:00 am-08:50 am

  Characterization of Goebner's basis.

  References
  Exercises
  Reading

  Characterization of Goebner's basis.
  

  References:

  None

  • Meeting 31 : Tue, Sep 27, 05:15 pm-06:15 pm

  Buchberger's characterization of Groebner basis. Algorithm for computing Grobner Basis.

  References
  Exercises
  Reading

  Buchberger's characterization of Groebner basis. Algorithm for computing Grobner Basis.
  

  References:

  None

  • Meeting 32 : Wed, Sep 28, 06:00 am-06:00 am

  Applications of Groebner basis.

  References
  Exercises
  Reading

  Applications of Groebner basis.
  

  References:

  None

• Theme 4 : Efficient Computations over polynomials - 21 meetings

  • Meeting 33 : Mon, Oct 03, 09:00 am-09:50 am

  Implicit Representation of polynomials. Arithmetic circuits.

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff. "Arithmetic Circuits: A survey of recent results and open questions"
  Exercises
  Reading

  Implicit Representation of polynomials. Arithmetic circuits.
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff. "Arithmetic Circuits: A survey of recent results and open questions"

  • Meeting 34 : Tue, Oct 04, 08:00 am-08:50 am

  Size and depth of arithmetic circuits. Representing Elementary symmetric polynomials: Ben-Or and Cleve's construction.

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Size and depth of arithmetic circuits. Representing Elementary symmetric polynomials: Ben-Or and Cleve's construction.
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 35 : Tue, Oct 04, 05:15 pm-06:30 pm

  Representing Determinant. Structural aspects: Homogeneous circuits. Depth reduction.

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Representing Determinant. Structural aspects: Homogeneous circuits. Depth reduction.
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 36 : Wed, Oct 05, 06:00 am-06:00 am

  Homogenization. Fan in restrictions. D

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Homogenization. Fan in restrictions. D
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 37 : Mon, Oct 17, 09:00 am-09:50 am

  Depth reduction for formulas. Depth reduction for general arithmetic circuits.

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Depth reduction for formulas. Depth reduction for general arithmetic circuits.
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 38 : Tue, Oct 18, 08:00 am-08:50 am

  Depth Reduction for general arithmetic circuits.

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Depth Reduction for general arithmetic circuits.
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 39 : Tue, Oct 18, 05:00 pm-06:40 pm

  Depth Reduction for general arithmetic circuits (contd)

  References	A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.
  Exercises
  Reading

  Depth Reduction for general arithmetic circuits (contd)
  

  References:

  A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff.

  • Meeting 40 : Wed, Oct 19, 12:00 pm-12:50 pm

  Branching programs.

  References
  Exercises
  Reading

  Branching programs.
  

  References:

  None

  • Meeting 41 : Mon, Oct 24, 09:00 am-09:50 am

  ABP vs Arithmetic Circuits. ABPs vs Arithmetic Formulas. Branching program for the determinant polynomial.

  References	Your class notes.Also, the original<a href="http://www.cse.iitk.ac.in/users/manindra/CS642/determinant.pdf" > article </a> by Mahajan and Vinay
  Exercises
  Reading

  ABP vs Arithmetic Circuits. ABPs vs Arithmetic Formulas. Branching program for the determinant polynomial.
  

  References:

  Your class notes.Also, the original article by Mahajan and Vinay

  • Meeting 42 : Tue, Oct 25, 10:00 am-11:00 am

  (Slot exchange with D slot) Branching program for the determinant polynomial. Width three simulation of arithmetic formulas.

  References
  Exercises
  Reading

  (Slot exchange with D slot) Branching program for the determinant polynomial. Width three simulation of arithmetic formulas.
  

  References:

  None

  • Meeting 43 : Tue, Oct 25, 05:00 pm-06:30 pm

  Branching program for the determinant polynomial. (contd) Width three simulation of arithmetic formulas.

  References	Original <a href=""> article</a> by Ben-Or and Cleve.
  Exercises
  Reading

  Branching program for the determinant polynomial. (contd) Width three simulation of arithmetic formulas.
  

  References:

  Original article by Ben-Or and Cleve.

  • Meeting 44 : Wed, Oct 26, 06:00 am-06:00 am

  Algorithmic questions on arithmetic circuits: Polynomial Identity Testing.

  References
  Exercises
  Reading

  Algorithmic questions on arithmetic circuits: Polynomial Identity Testing.
  

  References:

  None

  • Meeting 45 : Mon, Oct 31, 09:00 am-09:50 am

  Identity testing of univariate polynomials. A randomized algorithm. Reducing the case of n-variate polynomials to that of univariate. Resulting randomized algorithms. Limitations: it requires exponential space.

  References
  Exercises
  Reading

  Identity testing of univariate polynomials. A randomized algorithm. Reducing the case of n-variate polynomials to that of univariate. Resulting randomized algorithms. Limitations: it requires exponential space.
  

  References:

  None

  • Meeting 46 : Tue, Nov 01, 08:00 am-08:50 am

  Identity testing: Schwartz-Zippel Lemma. Another randomized algorithm.

  References
  Exercises
  Reading

  Identity testing: Schwartz-Zippel Lemma. Another randomized algorithm.
  

  References:

  None

  • Meeting 47 : Tue, Nov 01, 05:00 pm-06:30 pm

  Other algorithmic questions over arithmetic circuits: Polynomial factorization, Polynomial Equivalence, Polynomial Isomorphism, Computation of Coefficients, Testing Homgeneity, testing Multilinearity.

  References
  Exercises
  Reading

  Other algorithmic questions over arithmetic circuits: Polynomial factorization, Polynomial Equivalence, Polynomial Isomorphism, Computation of Coefficients, Testing Homgeneity, testing Multilinearity.
  

  References:

  None

  • Meeting 48 : Wed, Nov 02, 12:00pm-12:50pm

  Application of Identity testing to primality testing.

  References
  Exercises
  Reading

  Application of Identity testing to primality testing.
  

  References:

  None

  • Meeting 49 : Mon, Nov 07, 09:00 am-09:50 am

  Identity Testing for Sparse polynomials.

  References
  Exercises
  Reading

  Identity Testing for Sparse polynomials.
  

  References:

  None

  • Meeting 50 : Tue, Nov 08, 08:00 am-08:50 am

  Identity testing for non-commutative polynomials.

  References
  Exercises
  Reading

  Identity testing for non-commutative polynomials.
  

  References:

  None

  • Meeting 51 : Tue, Nov 08, 05:30 pm-06:45 pm

  Non-commutative PIT - continued.

  References
  Exercises
  Reading

  Non-commutative PIT - continued.
  

  References:

  None

  • Meeting 52 : Wed, Nov 09, 06:00 am-06:00 am

  Open questions on arithmetic circuits. Review of the course.

  References
  Exercises
  Reading

  Open questions on arithmetic circuits. Review of the course.
  

  References:

  None

  • Meeting 53 : Fri, Nov 11, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 5 : Evaluation Meetings. - 8 meetings

  • Meeting 54 : Sat, Oct 01, 09:00 am-10:30 am

  Mid sem. Syllabus Lectures 1 - 32 (i.e., until Wed 28 Sep).

  References
  Exercises
  Reading

  Mid sem. Syllabus Lectures 1 - 32 (i.e., until Wed 28 Sep).
  

  References:

  None

  • Meeting 55 : Wed, Nov 02, 02:00 pm-03:00 pm

  Pre-presentation meetings: Hrudaya Sahoo 2-2:20 Shom Abraham 2:20-2:40 Dikesh 2:40-3:00pm

  References
  Exercises
  Reading

  Pre-presentation meetings: Hrudaya Sahoo 2-2:20 Shom Abraham 2:20-2:40 Dikesh 2:40-3:00pm
  

  References:

  None

  • Meeting 56 : Sat, Nov 05, 02:00 pm-03:00 pm

  Hrudaya R Sahoo.

  References
  Exercises
  Reading

  Hrudaya R Sahoo.
  

  References:

  None

  • Meeting 57 : Sat, Nov 05, 04:00 pm-05:00 pm

  Shom Abraham

  References
  Exercises
  Reading

  Shom Abraham
  

  References:

  None

  • Meeting 58 : Sat, Nov 05, 05:00 pm-06:00 pm

  Dikesh C

  References
  Exercises
  Reading

  Dikesh C
  

  References:

  None

  • Meeting 59 : Thu, Nov 10, 02:00 pm-03:00 pm

  Mohit Daga

  References
  Exercises
  Reading

  Mohit Daga
  

  References:

  None

  • Meeting 60 : Thu, Nov 10, 06:00 pm-07:00 pm

  Santhoshini V

  References
  Exercises
  Reading

  Santhoshini V
  

  References:

  None

  • Meeting 61 : Wed, Nov 16, 02:00 pm-04:15 pm

  End Sem. Syllabus: Everything done in the class.

  References
  Exercises
  Reading

  End Sem. Syllabus: Everything done in the class.
  

  References:

  None