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**- 3 meetings- Meeting 01 : Wed, Jul 30, 02:00 pm-04:00 pm
- Meeting 02 : Fri, Aug 01, 03:00 pm-05:00 pm
- Meeting 03 : Wed, Aug 13, 02:00 pm-04:00 pm

Administrative announcements. Some example applications of algebraic algorithms: 1) Perfect Matching 2) Primality Testing 3) k-colorings of graphs. References Exercises Reading Administrative announcements. Some example applications of algebraic algorithms: 1) Perfect Matching 2) Primality Testing 3) k-colorings of graphs.References: None Introduction to Groups, Rings and Fields. Rings: More examples. Integral Domains and Fields. Ideals. First properties of ideals: finite generation (Hilbert's Basis theorem), Geometric Significance of ideals. References Herstein's Book on Algebra or Michael Artin's Algebra are good references for basic algebraic structures. There are several other excellent books on Modern Algebra. You could refer to any of them. Exercises Reading Introduction to Groups, Rings and Fields. Rings: More examples. Integral Domains and Fields. Ideals. First properties of ideals: finite generation (Hilbert's Basis theorem), Geometric Significance of ideals.References: Herstein's Book on Algebra or Michael Artin's Algebra are good references for basic algebraic structures. There are several other excellent books on Modern Algebra. You could refer to any of them. Rings and Fields. The polynomial ring. Ideals, and their relation to geometry. References Michael Artin, <i>Algebra</i> is a good reference to basic algebra. Exercises Reading Rings and Fields. The polynomial ring. Ideals, and their relation to geometry.References: Michael Artin, *Algebra*is a good reference to basic algebra.**Theme 2 : Algorithms for Division: Groebner Bases**- 7 meetings- Meeting 04 : Thu, Aug 14, 04:30 pm-05:45 pm
- Meeting 05 : Wed, Aug 20, 02:00 pm-04:00 pm
- Meeting 06 : Thu, Aug 21, 04:50 pm-05:45 pm
- Meeting 07 : Sat, Aug 23, 09:00 am-11:30 am
- Meeting 08 : Wed, Aug 27, 01:45 pm-02:50 pm
- Meeting 09 : Wed, Sep 03, 02:00 pm-04:15 pm
- Meeting 10 : Thu, Sep 04, 04:45 pm-06:15 pm

Hilbert's basis theorem. References [AL] Section 1.1. Exercises Reading Hilbert's basis theorem.References: [AL] Section 1.1. Hilbert's basis theorem (contd). Polynomial Division. The uni-variate case. Multivariate polynomial division. Need for ordering of terms. Various term orderings. References [AL] Sections 1.3 and 1.4. Exercises Reading Hilbert's basis theorem (contd). Polynomial Division. The uni-variate case. Multivariate polynomial division. Need for ordering of terms. Various term orderings.References: [AL] Sections 1.3 and 1.4. Example term orderings. Multivariate polynomial division. Introduction to Groebner bases. Definitions. Characterization. References [AL] Sections 1.5 and 1.6. Exercises Reading Example term orderings. Multivariate polynomial division. Introduction to Groebner bases. Definitions. Characterization.References: [AL] Sections 1.5 and 1.6. Groebner bases: existence. Buchberger's criterion for Grobner Basis. Computation of Groebner bases: Buchberger's algorithm. <i> Compensatory for Aug 6 &8 th</i> References [AL] Exercises Reading Groebner bases: existence. Buchberger's criterion for Grobner Basis. Computation of Groebner bases: Buchberger's algorithm.*Compensatory for Aug 6 &8 th*References: [AL] Cancelled to enable people to attend Aravind Srinivasan's lectures. <i> Short Lecture </i> References [AL] Exercises Reading Cancelled to enable people to attend Aravind Srinivasan's lectures.*Short Lecture*References: [AL] Bucherber's criterion (contd). Buchberger's Algorithm. Applications of Groebner Basis. Ideal Membership. Graph Coloring. References [AL] Exercises Reading Bucherber's criterion (contd). Buchberger's Algorithm. Applications of Groebner Basis. Ideal Membership. Graph Coloring.References: [AL] Application of Groebner Bases: Integer Programming. References [AL] Exercises Reading Application of Groebner Bases: Integer Programming.References: [AL] **Theme 3 : Algorithms for Factorizing Polynomials**- 13 meetings- Meeting 11 : Wed, Sep 10, 02:00 pm-04:15 pm
- Meeting 12 : Sun, Sep 14, 11:00 am-11:45 am
- Meeting 13 : Sun, Sep 14, 11:45 am-12:30 pm
- Meeting 14 : Wed, Sep 17, 02:00 pm-04:00 pm
- Meeting 15 : Thu, Sep 18, 04:30 pm-06:00 pm
- Meeting 16 : Tue, Sep 23, 02:00 pm-04:00 pm
- Meeting 17 : Wed, Sep 24, 02:00 pm-04:00 pm
- Meeting 18 : Tue, Sep 30, 02:00 pm-04:00 pm
- Meeting 19 : Wed, Oct 01, 02:00 pm-03:30 pm
- Meeting 20 : Wed, Oct 08, 02:00 pm-04:00 pm
- Meeting 21 : Thu, Oct 09, 04:30 pm-06:15 pm
- Meeting 22 : Sat, Oct 11, 09:00 pm-11:00 am
- Meeting 23 : Thu, Oct 16, 04:30 pm-06:00 pm

More algorithmic tasks on polynomials: The case of univariate polynomials. 1) Finding a root of a given polynomial. 2) Computing a factor of a given polynomial. When does a polynomial have root in the underlying field? Fundamental theorem of algebra. When do polynomials have unique factorization? Unique Factorization Domains. Gauss's Lemma. References See <a href="http://math.harvard.edu/~waffle/ufds2.pdf"> Notes</a> here. Exercises Reading More algorithmic tasks on polynomials: The case of univariate polynomials. 1) Finding a root of a given polynomial. 2) Computing a factor of a given polynomial. When does a polynomial have root in the underlying field? Fundamental theorem of algebra. When do polynomials have unique factorization? Unique Factorization Domains. Gauss's Lemma.References: See Notes here. Finite Fields, Field extensions and first properties. References <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes </a> Written by RP. Exercises Reading Finite Fields, Field extensions and first properties.References: Notes Written by RP. More on finite fields. The polynomial x^q-x. The distinct degree factorization problem. References <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes </a> Written by RP. Exercises Reading More on finite fields. The polynomial x^q-x. The distinct degree factorization problem.References: Notes Written by RP. Distinct degree factorization: Complete algorithm. Factorization of x^q-x. References <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes </a> Written by RP. <a href="http://www.cecm.sfu.ca/CAG/theses/chelsea.pdf"> Master's thesis </a> by Chelsea. Exercises Reading Distinct degree factorization: Complete algorithm. Factorization of x^q-x.References: Notes Written by RP. Master's thesis by Chelsea. Structure of quotient rings: Chinese remaindering theorem. Factorization over finite fields: Cantor-Zassenhaus Algorithm. References <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes </a> Written by RP. See Lectures 6 and 11. Also see [vGathen] Exercises Reading Structure of quotient rings: Chinese remaindering theorem. Factorization over finite fields: Cantor-Zassenhaus Algorithm.References: Notes Written by RP. See Lectures 6 and 11. Also see [vGathen] Cantor-Zassenhaus (Contd). Overview of other factorization algorithms: Berlekamp's algorithm. References <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes </a> Written by RP. Exercises Reading Cantor-Zassenhaus (Contd). Overview of other factorization algorithms: Berlekamp's algorithm.References: Notes Written by RP. Berlekamp's algorithm. References [vGathen] Book. <a href="http://www.cmi.ac.in/~ramprasad/lecturenotes/index.php?notes=cnt"> Notes</a> by RP. Exercises Reading Berlekamp's algorithm.References: [vGathen] Book. Notes by RP. An application of factorization: Construction of BCH codes. Multivariate polynomials: Computing the GCD, resultants. References [vGathen] Exercises Reading An application of factorization: Construction of BCH codes. Multivariate polynomials: Computing the GCD, resultants.References: [vGathen] Hensel's Lifting of factors and roots. Application to bivariate factorization. References <a href="http://people.csail.mit.edu/madhu/ST12/scribe/lect10.pdf"> Notes </a> by Madhu Sudan. Also see [vGathen]. Analogy with Newton Raphson is taken from <A href="http://www.cmi.ac.in/~ramprasad/lecturenotes/comp_numb_theory/lecture26.pdf"> Notes </a> by RP. Exercises Reading Hensel's Lifting of factors and roots. Application to bivariate factorization.Bivariate factorization. Cleaning up the factors after Hensel Lifting. References <a href="http://people.csail.mit.edu/madhu/ST12/scribe/lect10.pdf"> Notes </a> by Madhu Sudan. For factoring over Z, see [vGathen]. Exercises Reading Bivariate factorization. Cleaning up the factors after Hensel Lifting.References: Notes by Madhu Sudan. For factoring over Z, see [vGathen]. Factoring over integers. Mignotte's bound on coefficients. A factoring algorithm using large primes. Application of Hensel lifting. Introduction to Lattices. References [vGathen] Exercises Reading Factoring over integers. Mignotte's bound on coefficients. A factoring algorithm using large primes. Application of Hensel lifting. Introduction to Lattices.References: [vGathen] Lattice basis reduction. Application to integer factoring. LLL algorithm (description) References [vGathen] Exercises Reading Lattice basis reduction. Application to integer factoring. LLL algorithm (description)References: [vGathen] LLL algorithm: correctness proof. References [vGathen] Exercises Reading LLL algorithm: correctness proof.References: [vGathen] **Theme 4 : Succinct representation: Complexity and Algorithms**- 8 meetings- Meeting 24 : Wed, Oct 15, 03:30 pm-05:00 pm
- Meeting 25 : Thu, Oct 23, 04:30 pm-06:15 pm
- Meeting 26 : Sat, Oct 25, 09:00 am-11:30 am
- Meeting 27 : Wed, Oct 29, 02:00 pm-04:00 pm
- Meeting 28 : Thu, Oct 30, 04:45 pm-06:15 pm
- Meeting 29 : Tue, Nov 04, 09:00 am-11:00 am
- Meeting 30 : Wed, Nov 05, 03:00 pm-05:30 pm
- Meeting 31 : Thu, Nov 06, 09:00 am-11:00 am

Implicit Representation of Polynomials: Arithmetic Circuits. Example: Elementary symmetric polynomials References <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" >Survey </a> article by Amir Shpilka and Yehudayoff. Exercises Reading Implicit Representation of Polynomials: Arithmetic Circuits. Example: Elementary symmetric polynomialsReferences: Survey article by Amir Shpilka and Yehudayoff. Arithmetic Circuits and Arithmetic Formula. Brent's Depth reduction. References <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" >Survey </a> article by Amir Shpilka and Yehudayoff. Exercises Reading Arithmetic Circuits and Arithmetic Formula. Brent's Depth reduction.References: Survey article by Amir Shpilka and Yehudayoff. Programs with three registers: Ben-Or and Cleve. More on structure of arithmetic circuits:VSBR (only a sketch of the proof). References <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" >Survey </a> article by Amir Shpilka and Yehudayoff. Ben-Or and Cleve's simulation is given in <a href="http://people.csail.mit.edu/madhu/ST05/scribe/lect04.ps">Notes <a> by Madhu Sudan. Original <a href="http://maths-people.anu.edu.au/~brent/pd/rpb022.pdf">article </a> by Brent. Exercises Reading Programs with three registers: Ben-Or and Cleve. More on structure of arithmetic circuits:VSBR (only a sketch of the proof).References: Survey article by Amir Shpilka and Yehudayoff. Ben-Or and Cleve's simulation is given in Notes by Madhu Sudan. Original article by Brent. Computational Problems: Polynomial identity testing. A randomized algorithm:Schwartz-Zippel. Agrawal-Biswas approach to primality. AKS primality via identity test (introduction). References <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" >Survey </a> article by Amir Shpilka and Yehudayoff.. For Agrawal Biswas approach see the Section 3 of the original <a href="http://dl.acm.org/citation.cfm?id=792540"> atricle</a> Exercises Reading Computational Problems: Polynomial identity testing. A randomized algorithm:Schwartz-Zippel. Agrawal-Biswas approach to primality. AKS primality via identity test (introduction).AKS continued References See the original article " PRIMES is in P" by Agrawal-Kayal-Saxena. Exercises Reading AKS continuedReferences: See the original article " PRIMES is in P" by Agrawal-Kayal-Saxena. AKS (contd). References Exercises Reading AKS (contd).References: None More on identity testing: Importance of special classes of circuits. Depth 4 circuits vs the rest. An identity test for depth 3 circuits with bounded top fan-in (With a sketch of the proof). References <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" >Survey </a> article by Amir Shpilka and Yehudayoff. Exercises Reading More on identity testing: Importance of special classes of circuits. Depth 4 circuits vs the rest. An identity test for depth 3 circuits with bounded top fan-in (With a sketch of the proof).References: Survey article by Amir Shpilka and Yehudayoff. PIT for Noncommutative formulas. Applications to diagonal circuits. References Survey by Shpilka Yehudayoff. Exercises Reading PIT for Noncommutative formulas. Applications to diagonal circuits.References: Survey by Shpilka Yehudayoff. **Theme 5 : Evaluation Meetings**- 3 meetings- Meeting 32 : Sun, Sep 14, 09:30 am-11:00 am
- Meeting 33 : Wed, Oct 15, 02:00 pm-03:30 pm
- Meeting 34 : Wed, Nov 12, 02:00 pm-05:00 pm

QUIZ-1. <br> Syllabus: Lectures 1-09. References Exercises Reading QUIZ-1.

Syllabus: Lectures 1-09.References: None Quiz-2. Syllabus Lectures 10-21 References [vGathen] Lecture notes from RP, Madhu Sudan. See individual lectures for exact references. Exercises Reading Quiz-2. Syllabus Lectures 10-21References: [vGathen] Lecture notes from RP, Madhu Sudan. See individual lectures for exact references. End Semester Exam. Syllabus:Everything. References Exercises Reading End Semester Exam. Syllabus:Everything.References: None