Document Open Access Logo

Reconstruction of Real Depth-3 Circuits with Top Fan-In 2

Author Gaurav Sinha

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.31.pdf
  • Filesize: 1 MB
  • 53 pages

Document Identifiers

Author Details

Gaurav Sinha

Cite As Get BibTex

Gaurav Sinha. Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 31:1-31:53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.31

Abstract

Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing SigmaPiSigma(2) circuits over F (char(F)=0), i.e. depth-3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic 0.

The algorithm needs only a blackbox query access to the polynomial f in F[x_1,..., x_n] of degree d, computable by a SigmaPiSigma(2) circuit C. In addition, we assume that the "simple rank" of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time poly(n,d) and returns an equivalent SigmaPiSigma(2) circuit (with high probability).

The problem of reconstructing SigmaPiSigma(2) circuits over finite fields was first proposed by Shpilka [Shpilka, STOC 2007]. The generalization to SigmaPiSigma(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [Karnin/Shpilka, CCC 2015]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus the running time depends on the size of the field F. Their reconstruction algorithm uses lower bounds on the lengths of Linear Locally Decodable Codes with 2 queries. In our settings, such ideas immediately pose a problem and we need new ideas to handle the case of the characteristic 0 field F.

Our main techniques are based on the use of Quantitative Sylvester Gallai Theorems from the work of Barak et al. [Barak/Dvir/Wigderson/Yehudayoff, STOC 2011] to find a small collection of "nice" subspaces to project onto. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the "nice" subspaces can be "glued". We also use Brill's Equations from [Gelfand/Kapranov/Zelevinsky, 1994] to construct a small set of candidate linear forms (containing linear forms from both gates). Another important technique which comes very handy is the polynomial time randomized algorithm for factoring multivariate polynomials given by Kaltofen [Kaltofen/Trager, J. Symb. Comp. 1990].

Subject Classification

Keywords
  • Reconstruction
  • SigmaPiSigma(2)
  • Sylvester-Gallai
  • Brill's Equations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, volume 3821 of Lecture, pages 92-105. Springer, 2005. Google Scholar
  2. V. Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan. New results on noncommutative and commutative polynomial identity testing. 2012 IEEE 27th Conference on Computational Complexity, 0:268-279, 2008. URL: http://dx.doi.org/10.1109/CCC.2008.22.
  3. B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC'11, pages 519-528, New York, NY, USA, 2011. ACM. Google Scholar
  4. Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. J. ACM, 47(3):506-530, May 2000. URL: http://dx.doi.org/10.1145/337244.337257.
  5. B. Buchberger. A theoretical basis for the reduction of polynomials to canonical forms. SIGSAM Bull., 10(3):19-29, August 1976. URL: http://dx.doi.org/10.1145/1088216.1088219.
  6. Z. Dvir, S. Saraf, and A. Wigderson. Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of mathematics - Sigma (to appear), 2012. Google Scholar
  7. 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. Google Scholar
  8. Izrail Moiseevitch Gelfand, Mikhail M. Kapranov, and Andrei V. Zelevinsky. Discriminants, resultants, and multidimensional determinants. Mathematics: theory &applications. Birkhäuser, Boston, Basel, Berlin, 1994. Autre tirage de l'édition Birkhäuser chez Springer Science+ Business Media. Google Scholar
  9. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, August 1986. URL: http://dx.doi.org/10.1145/6490.6503.
  10. Ankit Gupta, Neeraj Kayal, and Satya Lokam. Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC'12, pages 625-642, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214035.
  11. Ankit Gupta, Neeraj Kayal, and Satyanarayana V. Lokam. Efficient reconstruction of random multilinear formulas. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 778-787, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.70.
  12. Ankit Gupta, Neeraj Kayal, and Youming Qiao. Random arithmetic formulas can be reconstructed efficiently. computational complexity, 23(2):207-303, 2014. URL: http://dx.doi.org/10.1007/s00037-014-0085-0.
  13. J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC'80, pages 262-272, New York, NY, USA, 1980. ACM. URL: http://dx.doi.org/10.1145/800141.804674.
  14. Erich Kaltofen and Barry M. Trager. Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comput., 9(3):301-320, March 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80015-6.
  15. Zohar S. Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24rd Annual CCC, pages 274-285, 2009. Google Scholar
  16. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS'09, pages 198-207, Washington, DC, USA, 2009. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2009.67.
  17. Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67-95, January 1994. URL: http://dx.doi.org/10.1145/174644.174647.
  18. Michael Kharitonov. Cryptographic lower bounds for learnability of boolean functions on the uniform distribution. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT'92, pages 29-36, New York, NY, USA, 1992. ACM. URL: http://dx.doi.org/10.1145/130385.130388.
  19. Adam Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory of computing, 2(10):185-206, 2006. Google Scholar
  20. Adam R. Klivans and Daniel Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC'01, pages 216-223, New York, NY, USA, 2001. ACM. URL: http://dx.doi.org/10.1145/380752.380801.
  21. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 2009(99):49-79, 2009. Google Scholar
  22. Nitin Saxena and C. Seshadhri. From sylvester-gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits. CoRR, abs/1002.0145, 2010. URL: http://arxiv.org/abs/1002.0145.
  23. Robert E. Schapire and Linda M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. In Proceedings of the Sixth Annual ACM Workshop on Computational Learning Theory, pages 17-26, 1996. Google Scholar
  24. Amir Shpilka. Interpolation of depth-3 arithmetic circuits with two multiplication gates. In STOC'07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 284-293. ACM Press, 2007. Google Scholar
  25. Amir Shpilka and Ilya Volkovich. Improved polynomial identity testing for read-once formulas. In APPROX-RANDOM, pages 700-713, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact