Lower Bounds for Non-Commutative Skew Circuits

by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan

Theory of Computing, Volume 12(12), pp. 1-38, 2016

Bibliography with links to cited articles

[1]   Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay: Non-commutative arithmetic circuits: Depth reduction and size lower bounds. Theoret. Comput. Sci., 209(1-2):47–86, 1998. Preliminary versions in DIMACS, FSTTCS’94 and STOC’93. [doi:10.1016/S0304-3975(97)00227-2]

[2]   Alexander Barvinok: New permanent estimators via non-commutative determinants, 2000. [arXiv:math/0007153]

[3]   Richard Beigel: When do extra majority gates help? Polylog(n) majority gates are equivalent to one. Comput. Complexity, 4(4):314–324, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01263420]

[4]   Peter Bürgisser, Joseph M. Landsberg, Laurent Manivel, and Jerzy Weyman: An overview of mathematical issues arising in the geometric complexity theory approach to VPVNP. SIAM J. Comput., 40(4):1179–1209, 2011. [doi:10.1137/090765328, arXiv:0907.2850]

[5]   Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen: Lower bounds for circuits with few modular and symmetric gates. In Proc. 32nd Internat. Colloq. on Automata, Languages and Programming (ICALP’05), volume 3580 of LNCS, pp. 994–1005. Springer, 2005. [doi:10.1007/11523468_80]

[6]   Xi Chen, Neeraj Kayal, and Avi Wigderson: Partial derivatives in arithmetic complexity and beyond. Found. Trends Theoret. Comput. Sci., 6(1-2):1–138, 2011. [doi:10.1561/0400000043]

[7]   Steve Chien, Lars Eilstrup Rasmussen, and Alistair Sinclair: Clifford algebras and approximating the permanent. J. Comput. System Sci., 67(2):263–290, 2003. Preliminary version in STOC’02. [doi:10.1016/S0022-0000(03)00010-2]

[8]   Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff: Separating multilinear branching programs and formulas. In Proc. 44th STOC, pp. 615–624. ACM Press, 2012. Preliminary version in ECCC. [doi:10.1145/2213977.2214034]

[9]   Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff: Non-commutative circuits and the sum-of-squares problem. J. Amer. Math. Soc., 24(3):871–898, 2011. Preliminary version in STOC’10. [doi:10.1090/S0894-0347-2011-00694-2]

[10]   Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff: Relationless completeness and separations. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 280–290. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.34]

[11]   Laurent Hyafil: The power of commutativity. In Proc. 18th FOCS, pp. 171–174. IEEE Comp. Soc. Press, 1977. [doi:10.1109/SFCS.1977.31]

[12]   Shachar Lovett and Srikanth Srinivasan: Correlation bounds for poly-size AC0 circuits with n1-o(1) symmetric gates. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), pp. 640–651. Springer, 2011. [doi:10.1007/978-3-642-22935-0_54]

[13]   Meena Mahajan and B. V. Raghavendra Rao: Small space analogues of Valiant’s classes and the limitations of skew formulas. Comput. Complexity, 22(1):1–38, 2013. Preliminary version in DROPS. [doi:10.1007/s00037-011-0024-2]

[14]   Guillaume Malod and Natacha Portier: Characterizing Valiant’s algebraic complexity classes. J. Complexity, 24(1):16–38, 2008. Preliminary version in MFCS’06. [doi:10.1016/j.jco.2006.09.006]

[15]   Noam Nisan: Lower bounds for non-commutative computation (extended abstract). In Proc. 23rd STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462]

[16]   Noam Nisan and Avi Wigderson: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217–234, 1996. Preliminary version in FOCS’95. [doi:10.1007/BF01294256]

[17]   Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1–8:17, 2009. Preliminary versions in STOC’04 and ECCC. [doi:10.1145/1502793.1502797]

[18]   Ran Raz, Amir Shpilka, and Amir Yehudayoff: A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. Comput., 38(4):1624–1647, 2008. Preliminary version in FOCS’07. [doi:10.1137/070707932]

[19]   Ran Raz and Amir Yehudayoff: Balancing syntactically multilinear arithmetic circuits. Comput. Complexity, 17(4):515–535, 2008. [doi:10.1007/s00037-008-0254-0]

[20]   Ran Raz and Amir Yehudayoff: Lower bounds and separations for constant depth multilinear circuits. Comput. Complexity, 18(2):171–207, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0270-8]

[21]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225]

[22]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theoret. Comput. Sci., 5(3-4):207–388, 2010. [doi:10.1561/0400000039]

[23]   Seinosuke Toda: Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. Systems, E75-D(1):116–124, 1992. IEICE.

[24]   Richard E. Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Symbolic and Algebraic Comput. (EUROSAM’79), volume 72 of LNCS, pp. 216–226, 1979. Available from Springer.