On Reconstruction and Testing of Read-Once Formulas

by Amir Shpilka and Ilya Volkovich

Theory of Computing, Volume 10(18), pp. 465-514, 2014

Bibliography with links to cited articles

[1]   Manindra Agrawal: Proving lower bounds via pseudo-random generators. In 25th Internat. Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’05), 2005, pp. 92–105, 2005. [doi:10.1007/11590156_6]

[2]   Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena: Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. In Proc. 44th STOC, pp. 599–614. ACM Press, 1980. [doi:10.1145/2213977.2214033, arXiv:1111.0582]

[3]   Matthew Anderson, Dieter van Melkebeek, and Ilya Volkovich: Derandomizing polynomial identity testing for multilinear constant-read formulae. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 273–282, 2011. See also at ECCC. [doi:10.1109/CCC.2011.18]

[4]   Dana Angluin, Lisa Hellerstein, and Marek Karpinski: Learning read-once formulas with queries. J. ACM, 40(1):185–210, 1993. Preliminary version in COLT’89. [doi:10.1145/138027.138061]

[5]   V. Arvind and Partha Mukhopadhyay: The monomial ideal membership problem and polynomial identity testing. Inform. and Comput., 208(4):351–363, 2010. See also at ECCC. [doi:10.1016/j.ic.2009.06.003]

[6]   Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio: Learning functions represented as multiplicity automata. J. ACM, 47(3):506–530, 2000. Preliminary version in FOCS’96. [doi:10.1145/337244.337257]

[7]   Michael Ben-Or and Prasoon Tiwari: A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In Proc. 20th STOC, pp. 301–309. ACM Press, 1988. [doi:10.1145/62212.62241]

[8]   Daoud Bshouty and Nader H. Bshouty: On interpolating arithmetic read-once formulas with exponentiation. J. Comput. System Sci., 56(1):112–124, 1998. Preliminary version in COLT’94. [doi:10.1006/jcss.1997.1550]

[9]   Nader H. Bshouty and Richard Cleve: Interpolating arithmetic read-once formulas in parallel. SIAM J. Comput., 27(2):401–413, 1998. [doi:10.1137/S009753979528812X]

[10]   Nader H. Bshouty, Thomas R. Hancock, and Lisa Hellerstein: Learning arithmetic read-once formulas. SIAM J. Comput., 24(4):706–735, 1995. Preliminary version in STOC’92. [doi:10.1137/S009753979223664X]

[11]   Nader H. Bshouty, Thomas R. Hancock, and Lisa Hellerstein: Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates. J. Comput. System Sci., 50(3):521–542, 1995. Preliminary version in COLT’92. [doi:10.1006/jcss.1995.1042]

[12]   Zeev Dvir and Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in STOC’05. [doi:10.1137/05063605X]

[13]   Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka: Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proc. 46th STOC, pp. 867–875. ACM Press, 2014. See also at ECCC. [doi:10.1145/2591796.2591816]

[14]   Michael A. Forbes and Amir Shpilka: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In Proc. 54th FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2013. See also at ECCC. [doi:10.1109/FOCS.2013.34]

[15]   Joachim von zur Gathen and Erich Kaltofen: Factoring sparse multivariate polynomials. J. Comput. System Sci., 31(2):265–287, 1985. Preliminary version in FOCS’83. [doi:10.1016/0022-0000(85)90044-3]

[16]   Dima Yu. Grigoriev, Marek Karpinski, and Michael F. Singer: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput., 19(6):1059–1063, 1990. [doi:10.1137/0219073]

[17]   Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam: Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Proc. 44th STOC, pp. 625–642. ACM Press, 1980. See also at ECCC. [doi:10.1145/2213977.2214035]

[18]   Thomas R. Hancock and Lisa Hellerstein: Learning read-once formulas over fields and extended bases. In Proc. 4th Ann. Workshop on Computational Learning Theory (COLT’91), pp. 326–336, 1991. [ACM:114867]

[19]   Joos Heintz and Claus-Peter Schnorr: Testing polynomials which are easy to compute (extended abstract). In Proc. 12th STOC, pp. 262–272. ACM Press, 1980. [doi:10.1145/800141.804674]

[20]   Lisa Hellerstein: Private communication, 2009.

[21]    Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity, 13(1-2):1–46, 2004. Preliminary version in STOC’03. See also at ECCC. [doi:10.1007/s00037-004-0182-6]

[22]   Mauricio Karchmer, Nati Linial, Ilan Newman, Mike Saks, and Avi Wigderson: Combinatorial characterization of read-once formulae. Discrete Mathematics, 114(1-3):275–282, 1993. [doi:10.1016/0012-365x(93)90372-z]

[23]   Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM J. Comput., 42(6):2114–2131, 2013. Preliminary version in STOC’10. [doi:10.1137/110824516]

[24]   Zohar Shay Karnin and Amir Shpilka: Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 274–285, 2009. Full version on author’s website. [doi:10.1109/ccc.2009.18]

[25]   Zohar Shay Karnin and Amir Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333–364, 2011. Preliminary version in CCC’08. [doi:10.1007/s00493-011-2537-3]

[26]   Neeraj Kayal and Shubhangi Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. See also at ECCC. [doi:10.1109/FOCS.2009.67]

[27]   Neeraj Kayal and Nitin Saxena: Polynomial identity testing for depth 3 circuits. Comput. Complexity, 16(2):115–138, 2007. Conference version at CCC’06. [doi:10.1007/s00037-007-0226-9]

[28]   Adam R. Klivans and Amir Shpilka: Learning restricted models of arithmetic circuits. Theory of Computing, 2(1):185–206, 2006. Preliminary version in COLT’03. [doi:10.4086/toc.2006.v002a010]

[29]   Adam R. Klivans and Daniel A. Spielman: Randomness efficient identity testing of multivariate polynomials. In Proc. 33rd STOC, pp. 216–223. ACM Press, 2001. [doi:10.1145/380752.380801]

[30]   Barbara Lhotzky: On the computational complexity of some algebraic counting problems. Ph.D. thesis, University of Bonn, Department of Computer Science, Bonn, Germany, 1991.

[31]   Richard J. Lipton and Nisheeth K. Vishnoi: Deterministic identity testing for multivariate polynomials. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 756–760. ACM Press, 2003. [ACM:644233]

[32]   Ran Raz and Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Comput. Complexity, 14(1):1–19, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0188-8]

[33]   Shubhangi Saraf and Ilya Volkovich: Black-box identity testing of depth-4 multilinear circuits. In Proc. 43rd STOC, pp. 421–430. ACM Press, 2011. See also at ECCC. [doi:10.1145/1993636.1993693]

[34]   Nitin Saxena: Diagonal circuit identity testing and lower bounds. In Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), pp. 60–71, 2008. See also at ECCC. [doi:10.1007/978-3-540-70575-8_6]

[35]   Nitin Saxena and C. Seshadhri: An almost optimal rank bound for depth-3 identities. SIAM J. Comput., 40(1):200–224, 2011. Preliminary version in CCC’09. See also at ECCC. [doi:10.1137/090770679]

[36]   Nitin Saxena and C. Seshadhri: Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter. SIAM J. Comput., 41(5):1285–1298, 2012. Preliminary version in STOC’11. See also at ECCC. [doi:10.1137/10848232]

[37]   Nitin Saxena and C. Seshadhri: From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33, 2013. Preliminary version in FOCS’10. See also at ECCC. [doi:10.1145/2528403]

[38]   Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. Preliminary version in ISSAC’79. [doi:10.1145/322217.322225]

[39]   Amir Shpilka: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. Comput., 38(6):2130–2161, 2009. Preliminary version in STOC’07. [doi:10.1137/070694879]

[40]   Amir Shpilka and Ilya Volkovich: Read-once polynomial identity testing. In Proc. 40th STOC, pp. 507–516. ACM Press, 2008. [doi:10.1145/1374376.1374448]

[41]   Amir Shpilka and Ilya Volkovich: Improved polynomial identity testing for read-once formulas. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 700–713, 2009. Full version at ECCC. [doi:10.1007/978-3-642-03685-9_52]

[42]   Amir Shpilka and Ilya Volkovich: On the relation between polynomial identity testing and finding variable disjoint factors. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 408–419, 2010. See also at ECCC. [doi:10.1007/978-3-642-14165-2_35]

[43]   Amir Shpilka and Ilya Volkovich: Read-once polynomial identity testing. Electron. Colloq. on Comput. Complexity (ECCC), 17:11, 2010. Full version of [41]. [ACM:1616551]

[44]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207–388, 2010. [doi:10.1561/0400000039]

[45]   Ilya Volkovich: Characterizing arithmetic read-once formulae. Manuscript, 2014. [arXiv:1408.1995]

[46]   Richard Zippel: Probabilistic algorithms for sparse polynomials. In Internat. Symp. Symbolic and Algebraic Computation (ISSAC’79), pp. 216–226, 1979. [doi:10.1007/3-540-09519-5_73]