Arithmetic Complexity in Ring Extensions

by Pavel Hrubeš and Amir Yehudayoff

Theory of Computing, Volume 7(8), pp. 119-129, 2011

Bibliography with links to cited articles

[1]   Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi: Algebraic complexity theory. Volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[2]   Peter Bürgisser, Thomas Lickteig, and Michael Shub: Test complexity of generic polynomials. J. Complexity, 8(3):203–215, 1992. [doi:10.1016/0885-064X(92)90022-4]

[3]   V. I. Danilov: Algebraic varieties and schemes. In I. R. Shafarevich, editor, Algebraic Geometry: Algebraic Curves, Algebraic Manifolds and Schemes, volume 23 of Algebraic Geometry I, Encyclopedia of Mathematical Sciences, pp. 167–297. Springer, 1994.

[4]   Zeev Dvir: Extractors for varieties. In Proc. 24th IEEE Conf. Comput. Complexity (CCC’09), pp. 102–113. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.7]

[5]   D. Grigoriev and A. Razborov: Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Engrg. Comm. Comput., 10(6):465–487, 2000. [doi:10.1007/s002009900021]

[6]   Dima Grigoriev, Marek Karpinski, and Andrew Chi-Chih Yao: An exponential lower bound on the size of algebraic decision trees for Max. Comput. Complexity, 7(3):193–203, 1998. [doi:10.1007/s000370050010]

[7]   P. Pudlák and V. Rödl: Some combinatorial-algebraic problems from complexity theory. Discrete Math., 136(1–3):253–279, 1994. [doi:10.1016/0012-365X(94)00115-Y]

[8]   René Schott and G. Stacey Staples: Reductions in computational complexity using Clifford algebras. Adv. in Appl. Clifford Algebr., 20:121–140, 2010. [doi:10.1007/s00006-008-0143-2]

[9]   Amir Shpilka and Avi Wigderson: Depth-3 arithmetic formulae over fields of characteristic zero. In Proc. IEEE 14th Conf. Comput. Complexity (CCC’99), pp. 87–96. IEEE Comp. Soc. Press, 1999. [doi:10.1109/CCC.1999.766267]

[10]   P. M. Spira: On time-hardware complexity tradeoffs for Boolean functions. In Proc. 4th. Hawaii Intern. Symp. Syst. Sciences., pp. 525–527, 1971.

[11]   Volker Strassen: Vermeidung von Divisionen. J. Reine Angew. Math., 264:184–202, 1973. [doi:10.1515/crll.1973.264.184]

[12]   Leslie G. Valiant: Graph-theoretic properties in computational complexity. J. Comput. System Sci., 13(3):278–285, 1976. [doi:10.1016/S0022-0000(76)80041-4]

[13]   Hugh E. Warren: Lower bounds for approximations by nonlinear manifolds. Trans. Amer. Math. Soc., 133:167–178, 1968. [doi:10.2307/1994937]