Theory of Computing Reading Seminar
Fall 2009

TIME AND PLACE:   Every Wednesday, 9:30am, CoRE 433.

Meetings

DATE PAPER TITLE
Sep 16, 23 Ran Raz. "Elusive Functions and Lower Bounds for Arithmetic Circuits." Proceeding of the 40th STOC, 2008.
Sep 30, Oct 7, Oct 14 Avi Wigderson. "Arithmetic Complexity - A Survey." Lecture notes, 2002.
Oct 14, Oct 21, Oct 28 Noam Nisan, Avi Wigderson. " Lower Bounds on Arithmetic Circuits via Partial Derivatives." Computational Complexity, vol. 6, pp. 217-234, 1996.
Oct 28, Nov 4, Nov 11, Nov 18 Neeraj Kayal, Shubhangi Saraf. "Blackbox Polynomial Identity Testing for Depth 3 Circuits." FOCS, 2009.

Possible future papers

Noam Nisan. "Lower Bounds for Non-Commutative Computation." STOC, 1991.
Ran Raz. "Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size." JACM 56(2) (2009).
Amir Shpilka, Avi Wigderson. " Depth-3 Arithmetic Formulae over Fields of Characteristic Zero." Journal of Computational Complexity, vol. 10, no. 1, pp. 1-27, 2001.
Ran Raz, Amir Shpilka, Amir Yehudayoff. "A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits." SIAM J. Comput. 38 (4), pages 1624-1647, 2008.
Ran Raz, Amir Yehudayoff. "Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors." Proceedings of the 49th FOCS, 2008.
Ran Raz, Amir Yehudayoff. "Lower Bounds and Separations for Constant Depth Mutilinear Circuits." Proceedings of Computational Complexity, 2008.
Dima Grigoriev, Alexander A. Razborov. "Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields." Appl. Algebra Eng. Commun. Comput. 10(6): 465-487 (2000).
Manindra Agrawal, V Vinay. "Arithmetic Circuits: A Chasm at Depth Four." FOCS, 2008.

HTML 4.01 Strict