- Meeting 33 : Mon, Oct 03, 09:00 am-09:50 am
References | |
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
References | |
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
References | |
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
References | |
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
References | |
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
References | |
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
References | |
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
References | |
Exercises | |
Reading | |
Branching programs.
- Meeting 41 : Mon, Oct 24, 09:00 am-09:50 am
References | |
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
References | |
Exercises | |
Reading | |
(Slot exchange with D slot)
Branching program for the determinant polynomial.
Width three simulation of arithmetic formulas.
- Meeting 43 : Tue, Oct 25, 05:00 pm-06:30 pm
References | |
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
References | |
Exercises | |
Reading | |
Algorithmic questions on arithmetic circuits: Polynomial Identity Testing.
- Meeting 45 : Mon, Oct 31, 09:00 am-09:50 am
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.
- Meeting 46 : Tue, Nov 01, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Identity testing: Schwartz-Zippel Lemma. Another randomized algorithm.
- Meeting 47 : Tue, Nov 01, 05:00 pm-06:30 pm
References | |
Exercises | |
Reading | |
Other algorithmic questions over arithmetic circuits: Polynomial factorization, Polynomial Equivalence, Polynomial Isomorphism, Computation of Coefficients, Testing Homgeneity, testing Multilinearity.
- Meeting 48 : Wed, Nov 02, 12:00pm-12:50pm
References | |
Exercises | |
Reading | |
Application of Identity testing to primality testing.
- Meeting 49 : Mon, Nov 07, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Identity Testing for Sparse polynomials.
- Meeting 50 : Tue, Nov 08, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Identity testing for non-commutative polynomials.
- Meeting 51 : Tue, Nov 08, 05:30 pm-06:45 pm
References | |
Exercises | |
Reading | |
Non-commutative PIT - continued.
- Meeting 52 : Wed, Nov 09, 06:00 am-06:00 am
References | |
Exercises | |
Reading | |
Open questions on arithmetic circuits. Review of the course.
- Meeting 53 : Fri, Nov 11, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced