Abstract
We study the problem of testing if the polynomial computed by an arithmetic circuit is identically zero (ACIT). We give a deterministic polynomial time algorithm for this problem when the inputs are read-twice formulas. This algorithm also computes the MLIN predicate, testing if the input circuit computes a multilinear polynomial.
We further study two related computational problems on arithmetic circuits. Given an arithmetic circuit C, 1) ZMC: test if a given monomial in C has zero coefficient or not, and 2) MonCount: compute the number of monomials in C. These problems were introduced by Fournier, Malod and Mengel [STACS 2012], and shown to characterize various levels of the counting hierarchy (CH).
We address the above problems on read-restricted arithmetic circuits and branching programs. We prove several complexity characterizations for the above problems on these restricted classes of arithmetic circuits.
Partially supported by Indo-German Max Planck Center (IMPECS).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Saha, C., Saptharishi, R., Saxena, N.: Jacobian hits circuits: Hitting-sets, lower bounds for depth-d occur-k formulas & depth-3 transcendence degree-k circuits. In: STOC (to Appear, 2012)
Agrawal, M., Vinay, V.: Arithmetic circuits: A chasm at depth four. In: FOCS, pp. 67–75 (2008)
Allender, E.: Arithmetic circuits and counting complexity classes. In: Krajicek, J. (ed.) Complexity of Computations and Proofs, Quaderni di Matematica, vol. 13, pp. 33–72. Seconda Universita di Napoli (2004)
Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Computational Complexity 8(2), 99–126 (1999)
Anderson, M., van Melkebeek, D., Volkovich, I.: Derandomizing polynomial identity testing for multilinear constant-read formulae. In: CCC, pp. 273–282 (2011)
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)
Buss, S.: The Boolean formula value problem is in ALOGTIME. In: STOC, pp. 123–131 (1987)
Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM Journal of Computation 21(4), 755–780 (1992)
Caussinus, H., McKenzie, P., Thérien, D., Vollmer, H.: Nondeterministic NC1 computation. Journal of Computer and System Sciences 57, 200–212 (1998)
Datta, S., Mahajan, M., Rao, B.V.R., Thomas, M., Vollmer, H.: Counting classes and the fine structure between NC1 and L. Theoretical Computer Science 417, 36–49 (2012)
Fournier, H., Malod, G., Mengel, S.: Monomials in arithmetic circuits: Complete problems in the counting hierarchy. In: STACS (to appear, 2012)
Jansen, M.J., Qiao, Y., Sarma, J.M.N.: Deterministic black-box identity testing π-ordered algebraic branching programs. In: FSTTCS, pp. 296–307 (2010)
Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1-2), 1–46 (2004)
Koiran, P., Perifel, S.: The complexity of two problems on arithmetic circuits. Theoretical Computer Science 389(1-2), 172–181 (2007)
Shpilka, A., Volkovich, I.: Read-once polynomial identity testing. In: STOC, pp. 507–516 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mahajan, M., Rao, B.V.R., Sreenivasaiah, K. (2012). Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. In: Rovan, B., Sassone, V., Widmayer, P. (eds) Mathematical Foundations of Computer Science 2012. MFCS 2012. Lecture Notes in Computer Science, vol 7464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32589-2_57
Download citation
DOI: https://doi.org/10.1007/978-3-642-32589-2_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32588-5
Online ISBN: 978-3-642-32589-2
eBook Packages: Computer ScienceComputer Science (R0)