Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Introduction**- 5 meetings- Meeting 01 : Tue, Aug 02, 08:00 am-08:50 am
- Meeting 02 : Wed, Aug 03, 06:00 am-06:00 am
- Meeting 03 : Fri, Aug 05, 11:00 am-11:50 am
- Meeting 04 : Mon, Aug 08, 09:00 am-09:50 am
- Meeting 05 : Tue, Aug 09, 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. 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 Introduction to Groups. Definition. Lagrange's theorem. References Exercises Reading Introduction to Groups. Definition. Lagrange's theorem.References: None Cosets. Normal Subgroup. Homomorphisms. References Exercises Reading Cosets. Normal Subgroup. Homomorphisms.References: None 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
- Meeting 07 : Fri, Aug 12, 11:00 am-11:50 am
- Meeting 08 : Tue, Aug 16, 08:00 am-08:50 am
- Meeting 09 : Wed, Aug 17, 06:00 am-06:00 am
- Meeting 10 : Thu, Aug 18, 09:00 am-09:50 am
- Meeting 11 : Fri, Aug 19, 11:00 am-11:50 am
- Meeting 12 : Mon, Aug 22, 09:00 am-09:50 am
- Meeting 13 : Tue, Aug 23, 08:00 am-08:50 am
- Meeting 14 : Wed, Aug 24, 06:00 am-06:00 am
- Meeting 15 : Fri, Aug 26, 11:00 am-11:50 am
- Meeting 16 : Mon, Aug 29, 09:00 am-09:50 am
- Meeting 17 : Tue, Aug 30, 08:00 am-08:50 am
- Meeting 18 : Wed, Aug 31, 06:00 am-06:00 am
- Meeting 19 : Fri, Sep 02, 11:00 am-11:50 am
- Meeting 20 : Tue, Sep 06, 08:00 am-08:50 am

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 Graph Automorpsim vs Graph Isomorphism. Colored graph isomorphism. References Exercises Reading Graph Automorpsim vs Graph Isomorphism. Colored graph isomorphism.References: None 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. 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] 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. Blocks. Primitive groups. A characterization of primitive groups. References [Arv] Exercises Reading Blocks. Primitive groups. A characterization of primitive groups.References: [Arv] Characterization of primitive transitive groups. References [Arv] Exercises Reading Characterization of primitive transitive groups.References: [Arv] 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. 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]. 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] Bounded valence GI (contd) References [Arv] Exercises Reading Bounded valence GI (contd)References: [Arv] 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] 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]. Bounded color multiplicity GI (contd). Application to general GI. References Exercises Reading Bounded color multiplicity GI (contd). Application to general GI.References: None 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
- Meeting 22 : Fri, Sep 09, 11:00 am-11:50 am
- Meeting 23 : Mon, Sep 12, 12:00 pm-12:50 pm
- Meeting 24 : Wed, Sep 14, 06:00 am-06:00 am
- Meeting 25 : Fri, Sep 16, 11:00 am-11:50 am
- Meeting 26 : Mon, Sep 19, 09:00 am-09:50 am
- Meeting 27 : Tue, Sep 20, 08:00 am-08:50 am
- Meeting 28 : Wed, Sep 21, 06:00 am-06:00 am
- Meeting 29 : Fri, Sep 23, 11:00 am-11:50 am
- Meeting 30 : Tue, Sep 27, 08:00 am-08:50 am
- Meeting 31 : Tue, Sep 27, 05:15 pm-06:15 pm
- Meeting 32 : Wed, Sep 28, 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 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. 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. 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" 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" 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] 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. 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. 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 Characterization of Goebner's basis. References Exercises Reading Characterization of Goebner's basis.References: None 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 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
- Meeting 34 : Tue, Oct 04, 08:00 am-08:50 am
- Meeting 35 : Tue, Oct 04, 05:15 pm-06:30 pm
- Meeting 36 : Wed, Oct 05, 06:00 am-06:00 am
- Meeting 37 : Mon, Oct 17, 09:00 am-09:50 am
- Meeting 38 : Tue, Oct 18, 08:00 am-08:50 am
- Meeting 39 : Tue, Oct 18, 05:00 pm-06:40 pm
- Meeting 40 : Wed, Oct 19, 12:00 pm-12:50 pm
- Meeting 41 : Mon, Oct 24, 09:00 am-09:50 am
- Meeting 42 : Tue, Oct 25, 10:00 am-11:00 am
- Meeting 43 : Tue, Oct 25, 05:00 pm-06:30 pm
- Meeting 44 : Wed, Oct 26, 06:00 am-06:00 am
- Meeting 45 : Mon, Oct 31, 09:00 am-09:50 am
- Meeting 46 : Tue, Nov 01, 08:00 am-08:50 am
- Meeting 47 : Tue, Nov 01, 05:00 pm-06:30 pm
- Meeting 48 : Wed, Nov 02, 12:00pm-12:50pm
- Meeting 49 : Mon, Nov 07, 09:00 am-09:50 am
- Meeting 50 : Tue, Nov 08, 08:00 am-08:50 am
- Meeting 51 : Tue, Nov 08, 05:30 pm-06:45 pm
- Meeting 52 : Wed, Nov 09, 06:00 am-06:00 am
- Meeting 53 : Fri, Nov 11, 11:00 am-11: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" 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. 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. 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. DReferences: A general reference on arithmetic circuits is an excellent survey by Shpilka and Yehudayoff. 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. 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. 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. Branching programs. References Exercises Reading Branching programs.References: None 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 (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 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. Algorithmic questions on arithmetic circuits: Polynomial Identity Testing. References Exercises Reading Algorithmic questions on arithmetic circuits: Polynomial Identity Testing.References: None 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 Identity testing: Schwartz-Zippel Lemma. Another randomized algorithm. References Exercises Reading Identity testing: Schwartz-Zippel Lemma. Another randomized algorithm.References: None 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 Application of Identity testing to primality testing. References Exercises Reading Application of Identity testing to primality testing.References: None Identity Testing for Sparse polynomials. References Exercises Reading Identity Testing for Sparse polynomials.References: None Identity testing for non-commutative polynomials. References Exercises Reading Identity testing for non-commutative polynomials.References: None Non-commutative PIT - continued. References Exercises Reading Non-commutative PIT - continued.References: None Open questions on arithmetic circuits. Review of the course. References Exercises Reading Open questions on arithmetic circuits. Review of the course.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 5 : Evaluation Meetings.**- 8 meetings- Meeting 54 : Sat, Oct 01, 09:00 am-10:30 am
- Meeting 55 : Wed, Nov 02, 02:00 pm-03:00 pm
- Meeting 56 : Sat, Nov 05, 02:00 pm-03:00 pm
- Meeting 57 : Sat, Nov 05, 04:00 pm-05:00 pm
- Meeting 58 : Sat, Nov 05, 05:00 pm-06:00 pm
- Meeting 59 : Thu, Nov 10, 02:00 pm-03:00 pm
- Meeting 60 : Thu, Nov 10, 06:00 pm-07:00 pm
- Meeting 61 : Wed, Nov 16, 02:00 pm-04:15 pm

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 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:00pmReferences: None Hrudaya R Sahoo. References Exercises Reading Hrudaya R Sahoo.References: None Shom Abraham References Exercises Reading Shom AbrahamReferences: None Dikesh C References Exercises Reading Dikesh CReferences: None Mohit Daga References Exercises Reading Mohit DagaReferences: None Santhoshini V References Exercises Reading Santhoshini VReferences: None End Sem. Syllabus: Everything done in the class. References Exercises Reading End Sem. Syllabus: Everything done in the class.References: None