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 VP≠VNP. 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.