Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas In this article, we study the identity testing problem of arithmetic read-once formulas (ROFs) and some related models. An ROF is a formula (a circuit whose underlying graph is a tree) in which the operations are +, and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for ROFs, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of Shpilka and Yolkovich [51]. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

Download PDF
11 pages

Loading next page...
 
/lp/association-for-computing-machinery/complete-derandomization-of-identity-testing-and-reconstruction-of-dOyCZyJmPt
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3196836
Publisher site
See Article on Publisher Site

Abstract

In this article, we study the identity testing problem of arithmetic read-once formulas (ROFs) and some related models. An ROF is a formula (a circuit whose underlying graph is a tree) in which the operations are +, and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for ROFs, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of Shpilka and Yolkovich [51].

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 23, 2018

Keywords: Arithmetic circuit

References

  • Proving lower bounds via pseudo-random generators
    Agrawal, M.
  • PRIMES is in P
    Agrawal, M.; Kayal, N.; Saxena, N.
  • Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
    Agrawal, M.; Saha, C.; Saptharishi, R.; Saxena, N.
  • Quasi-polynomial hitting-set for set-depth-Delta formulas
    Agrawal, M.; Saha, C.; Saxena, N.
  • Combinatorial nullstellensatz
    Alon, N.
  • Identity testing and lower bounds for read-k oblivious algebraic branching programs
    Anderson, M.; Forbes, M. A.; Saptharishi, R.; Shpilka, A.; Volk, B. L.
  • Derandomizing polynomial identity testing for multilinear constant-read formulae
    Anderson, M.; van Melkebeek, D.; Volkovich, I.
  • Learning read-once formulas with queries
    Angluin, D.; Hellerstein, L.; Karpinski, M.
  • Proof verification and the hardness of approximation problems
    Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M.
  • Probabilistic checking of proofs: A new characterization of NP
    Arora, S.; Safra, S.
  • The monomial ideal membership problem and polynomial identity testing
    Arvind, V.; Mukhopadhyay, P.
  • Algebraic independence and blackbox identity testing
    Beecken, M.; Mittmann, J.; Saxena, N.
  • A deterministic algorithm for sparse multivariate polynominal interpolation
    Ben-Or, M.; Tiwari, P.
  • On interpolating arithmetic read-once formulas with exponentiation
    Bshouty, D.; Bshouty, N. H.
  • Interpolating arithmetic read-once formulas in parallel
    Bshouty, N. H.; Cleve, R.
  • Learning arithmetic read-once formulas
    Bshouty, N. H.; Hancock, T. R.; Hellerstein, L.
  • Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates
    Bshouty, N. H.; Hancock, T. R.; Hellerstein, L.
  • A probabilistic remark on algebraic program testing
    DeMillo, R. A.; Lipton, R. J.
  • Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
    Dvir, Z.; Shpilka, A.
  • Bipartite perfect matching is in quasi-NC
    Fenner, S. A.; Gurjar, R.; Thierauf, T.
  • Pseudorandomness for multilinear read-once algebraic branching programs, in any order
    Forbes, M. A.; Saptharishi, R.; Shpilka, A.
  • Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
    Forbes, M. A.; Shpilka, A.
  • Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs
    Forbes, M. A.; Shpilka, A.
  • Proof complexity lower bounds from algebraic circuit complexity
    Forbes, M. A.; Shpilka, A.; Tzameret, I.; Wigderson, A.
  • Algebraic geometric techniques for depth-4 PIT and Sylvester-Gallai conjectures for varieties
    Gupta, A.
  • Identity testing for constant-width, and commutative, read-once oblivious ABPs
    Gurjar, R.; Korwar, A.; Saxena, N.
  • Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
    Gurjar, R.; Korwar, A.; Saxena, N.; Thierauf, N.
  • Learning read-once formulas over fields and extended bases
    Hancock, T. R.; Hellerstein, L.
  • Testing polynomials which are easy to compute (extended abstract)
    Heintz, J.; Schnorr, C. P.
  • Combinatorial characterization of read-once formulae
    Karchmer, M.; Linial, N.; Newman, I.; Saks, M. E.; Wigderson, A.
  • Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in
    Karnin, Z. S.; Mukhopadhyay, P.; Shpilka, A.; Volkovich, I.
  • Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
    Karnin, Z. S.; Shpilka, A.
  • Blackbox polynomial identity testing for depth 3 circuits
    Kayal, N.; Saraf, S.
  • Polynomial identity testing for depth 3 circuits
    Kayal, N.; Saxena, N.
  • Randomness efficient identity testing of multivariate polynomials
    Klivans, A.; Spielman, D.
  • Arithmetic circuits with locally low algebraic rank
    Kumar, M.; Saraf, S.
  • Sums of products of polynomials in few variables: Lower bounds and polynomial identity testing
    Kumar, M.; Saraf, S.
  • Deterministic identity testing for multivariate polynomials
    Lipton, R. J.; Vishnoi, N. K.
  • On determinants, matchings, and random algorithms
    Lovasz, L.
  • Algebraic methods for interactive proof systems
    Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N.
  • Depth-4 identity testing and Noether’s normalization lemma
    Mukhopadhyay, P.
  • Matching is as easy as matrix inversion
    Mulmuley, K.; Vazirani, U.; Vazirani, V.
  • Diagonal circuit identity testing and lower bounds
    Saxena, N.
  • From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for deph-3 circuits
    Saxena, N.; Seshadhri, C.
  • An almost optimal rank bound for depth-3 identities
    Saxena, N.; Seshadhri, C.
  • Fast probabilistic algorithms for verification of polynomial identities
    Schwartz, J. T.
  • IP=PSPACE
    Shamir, A.
  • Read-once polynomial identity testing
    Shpilka, A.; Volkovich, I.
  • Improved polynomial identity testing for read-once formulas
    Shpilka, A.; Volkovich, I.
  • On reconstruction and testing of read-once formulas
    Shpilka, A.; Volkovich, I.
  • Read-once polynomial identity testing
    Shpilka, A.; Volkovich, I.
  • Arithmetic circuits: A survey of recent results and open questions
    Shpilka, A.; Yehudayoff, A.
  • Characterizing arithmetic read-once formulae
    Volkovich, I.
  • Probabilistic algorithms for sparse polynomials
    Zippel, R.