Document Open Access Logo

Arithmetic Circuits with Locally Low Algebraic Rank

Authors Mrinal Kumar, Shubhangi Saraf

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.34.pdf
  • Filesize: 0.65 MB
  • 27 pages

Document Identifiers

Author Details

Mrinal Kumar
Shubhangi Saraf

Cite As Get BibTex

Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 34:1-34:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.34

Abstract

In recent years there has been a flurry of activity proving lower bounds for  homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply VP != VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 arithmetic circuits. 

A  depth-4 circuit is a representation of an N-variate, degree n polynomial P as P = sum_{i=1}^T Q_{i1} * Q_{i2} * ... * Q_{it} where the Q_{ij} are given by their monomial expansion. Homogeneity adds the constraint that for every i in [T], sum_{j} degree(Q_{ij}) = n. We study an extension where, for every i in [T], the algebraic rank of the set of polynomials {Q_{i1},  Q_{i2}, ... ,Q_{it}} is at most some parameter k.  We call this the class of spnew circuits. Already for k=n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t<=n (and hence k<=n).

We study lower bounds and polynomial identity tests for such circuits and prove the following results. 

1. Lower bounds: We give an explicit family of polynomials {P_n} of degree n in N = n^{O(1)} variables in VNP, such that any spnewn circuit computing P_n has size at least exp{(Omega(sqrt(n)*log(N)))}. This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits [KLSS14, KS-full] as well as the Jacobian based lower bounds of Agrawal et al. which worked for spnew circuits in the restricted setting where  T * k <= n.  

2. Hitting sets: Let spnewbounded be the class of spnew circuits with bottom fan-in at most d. We show that if d and k are at most poly(log(N)), then there is an explicit hitting set for spnewbounded circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly(log(N)). 


A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.

Subject Classification

Keywords
  • algebraic independence
  • arithmetic circuits
  • lower bounds

Metrics

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

References

  1. M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, 2008. Google Scholar
  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 Proceedings of the 44th ACM symposium on Theory of computing, pages 599-614, 2012. Google Scholar
  3. Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, pages 137-148, 2011. Google Scholar
  4. Rafael Mendes de Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. Electronic Colloquium on Computational Complexity (ECCC), 21:157, 2014. Google Scholar
  5. Z. Dvir and A. Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM Journal on Computing, 36(5):1404-1434, 2006. Google Scholar
  6. Zeev Dvir, Ariel Gabizon, and Avi Wigderson. Extractors and rank extractors for polynomial sources. computational complexity, 18(1):1-58, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0258-4,
  7. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: http://dx.doi.org/10.1137/080735850,
  8. Michael Forbes. Deterministic divisibility testing via shifted partial derivatives. In FOCS, 2015. Google Scholar
  9. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 243-252, 2013. Google Scholar
  10. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 0:243-252, 2013. Google Scholar
  11. H. Fournier, N. Limaye, G. Malod, and S. Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In STOC, 2014. Google Scholar
  12. D. Grigoriev and A. Razborov. Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput., 10(6):465-487, 2000. Google Scholar
  13. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pages 577-582, 1998. Google Scholar
  14. A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Approaching the chasm at depth four. In CCC, 2013. Google Scholar
  15. Z. Karnin, P. Mukhopadhyay, A. Shpilka, and I. Volkovich. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. In Proceedings of the 42nd Annual STOC, pages 649-658, 2010. Google Scholar
  16. Z. Karnin and A. Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. In In proceedings of 23rd Annual CCC, pages 280-291, 2008. Google Scholar
  17. N. Kayal. The complexity of the annihilating polynomial. In Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on, pages 184-193, July 2009. URL: http://dx.doi.org/10.1109/CCC.2009.37.
  18. N. Kayal, N. Limaye, C. Saha, and S. Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In FOCS, 2014. Google Scholar
  19. N. Kayal and S. Saraf. Blackbox polynomial identity testing for depth 3 circuits. In Proceedings of the 50th Annual FOCS, pages 198-207, 2009. Google Scholar
  20. N. Kayal and N. Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. Google Scholar
  21. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. ECCC, 19:81, 2012. Google Scholar
  22. Neeraj Kayal and Chandan Saha. Lower bounds for depth three arithmetic circuits with small bottom fanin. Electronic Colloquium on Computational Complexity (ECCC), 21:89, 2014. URL: http://eccc.hpi-web.de/report/2014/089.
  23. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In STOC, 2014. Google Scholar
  24. P. Koiran. Arithmetic circuits : The chasm at depth four gets wider. TCS, 2012. Google Scholar
  25. Mrinal Kumar and Ramprasad Saptharishi. An exponential lower bound for homogeneous depth-5 circuits over finite fields. ECCC, 2015. Google Scholar
  26. Mrinal Kumar and Shubhangi Saraf. The limits of depth reduction for arithmetic formulas: It’s all about the top fan-in. In STOC, 2014. Google Scholar
  27. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. FOCS, 2014. Google Scholar
  28. Mrinal Kumar and Shubhangi Saraf. Sums of products of polynomials in few variables : lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 2015. Google Scholar
  29. James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press, Inc., New York, NY, USA, 2006. Google Scholar
  30. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(1):135-177, 2010. Google Scholar
  31. R. Saptharishi. Recent progress on arithmetic circuit lower bounds. Bulletin of the EATCS, 2014. Google Scholar
  32. R. Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Manuscript, 2014. Google Scholar
  33. S. Saraf and I. Volkovich. Black-box identity testing of depth-4 multilinear circuits. In Proceedings of the 43rd Annual STOC, pages 421-430, 2011. Google Scholar
  34. N. Saxena and C. Seshadhri. From sylvester-gallai configurations to rank bounds: Improved black-box identity test for deph-3 circuits. In Proceedings of the 51st Annual FOCS, pages 21-30, 2010. Google Scholar
  35. N. Saxena and C. Seshadhri. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter. SIAM Journal on Computing, 41(5):1285-1298, 2012. Google Scholar
  36. A. Shpilka and A. Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001. Google Scholar
  37. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, March 2010. URL: http://dx.doi.org/10.1561/0400000039.
  38. Amir Shpilka. Affine projections of symmetric polynomials. In Proceedings of the 16th Annual Conference on Computational Complexity, CCC '01, pages 160-, Washington, DC, USA, 2001. IEEE Computer Society. Google Scholar
  39. Amir Shpilka and Ilya Volkovich. Improved polynomial identity testing for read-once formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pages 700-713, 2009. Google Scholar
  40. Amir Shpilka and Ilya Volkovich. Improved polynomial identity testing of read-once formulas. In Approximation, Randomization and Combinatorial Optimization.Algorithms and Techniques, volume 5687 of LNCS, pages 700-713, 2009. URL: http://www.cs.technion.ac.il/~shpilka/publications/PROF.pdf.
  41. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. In MFCS, pages 813-824, 2013. Google Scholar
  42. L. G. Valiant. Completeness classes in algebra. In STOC, 1979. 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