Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring \({\mathbb{F}\langle{x_1,\ldots,x_N\rangle}}\), where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all non-commutative circuit models for which lower bounds are known. We prove several results about such circuits.

  1. 1.

    We show exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde et al. [Electronic Colloquium on Comput Complexity (ECCC) vol 23, no 94, 2016], who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. The polynomial we prove a lower bound for is in fact computable by a polynomial-sized non-commutative circuit.

  2. 2.

    We show exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye et al. (Theory Comput 12(1):1–38, 2016) and the above lower bounds of Lagarde et al. (2016), which are known to be incomparable. Here too, the hard polynomial is computable by a polynomial-sized non-commutative circuit.

  3. 3.

    We make progress on a question of Nisan (STOC, pp 410–418, 1991) regarding separating the power of Algebraic Branching Programs (ABPs) and Formulas in the non-commutative setting by showing a tight lower bound of \({n^{\Omega(\log d)}}\) for any UPT formula computing the product of d\({n \times n}\) matrices.

    When \({d \leq \log n}\), we can also prove superpolynomial lower bounds for formulas with up to \({2^{o(d)}}\) many parse trees (for computing the same polynomial). Improving this bound to allow for \({2^{o(d)}}\) trees would give an unconditional separation between ABPs and Formulas.

  4. 4.

    We give deterministic whitebox PIT algorithms for UPT circuits over any field, strengthening a result of Lagarde et al. (2016), and also for sums of a constant number of UPT circuits with different parse trees.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agrawal, Manindra, Gurjar, Rohit, Korwar, Arpita, Saxena, Nitin: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44(3), 669–697 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Allender, Eric, Jiao, Jia, Mahajan, Meena, Vinay, V.: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci. 209(1–2), 47–86 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  • Arvind, Vikraman, Datta, Rajit, Mukhopadhyay, Partha, Raja, S.: Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings. Electronic Colloquium on Computational Complexity (ECCC) 24, 74 (2017)

    Google Scholar 

  • Arvind, Vikraman, Joglekar, Pushkar S., Mukhopadhyay, Partha, Raja, S.: Identity Testing for +-Regular Noncommutative Arithmetic Circuits. Electronic Colloquium on Computational Complexity (ECCC) 23, 193 (2016a)

    Google Scholar 

  • Arvind, Vikraman, Joglekar, Pushkar S., Srinivasan, Srikanth: Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, 25–36 (2009)

    MathSciNet  MATH  Google Scholar 

  • Arvind, Vikraman, Mukhopadhyay, Partha, Raja, S.: Randomized Polynomial Time Identity Testing for Noncommutative Circuits. Electronic Colloquium on Computational Complexity (ECCC) 23, 89 (2016b)

    MATH  Google Scholar 

  • Arvind, Vikraman, Mukhopadhyay, Partha, Srinivasan, Srikanth: New Results on Noncommutative and Commutative Polynomial Identity Testing. Computational Complexity 19(4), 521–558 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Arvind, Vikraman, Raja, S.: The Complexity of Two Register and Skew Arithmetic Computation. Electronic Colloquium on Computational Complexity (ECCC) 21, 28 (2014)

    MATH  Google Scholar 

  • Andrej Bogdanov & Hoeteck Wee (2005). More on Noncommutative Polynomial Identity Testing. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 92–99

  • Chien, Steve, Rasmussen, Lars Eilstrup, Sinclair, Alistair: Clifford algebras and approximating the permanent. J. Comput. Syst. Sci. 67(2), 263–290 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Steve Chien & Alistair Sinclair (2004). Algebras with Polynomial Identities and Computing the Determinant. In 45th Symposium on Foundations of Computer Science (FOCS 2004), Proceedings, 352–361

  • Kenneth Church & Ramesh Patil (1982). Coping with Syntactic Ambiguity or How to Put the Block in the Box on the Table. Comput. Linguist. 8(3-4), 139–149. ISSN 0891-2017

  • Zeev Dvir, Guillaume Malod, Sylvain Perifel & Amir Yehudayoff (2012). Separating multilinear branching programs and formulas. In STOC, Howard J. Karloff & Toniann Pitassi, editors, 615–624. ACM. ISBN 978-1-4503-1245-5

  • Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira & Avi Wigderson (2018). Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, 1:1–1:19

  • Forbes, Michael A., Shpilka, Amir: 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 2013, 243–252 (2013)

    Google Scholar 

  • Fournier, Hervé, Limaye, Nutan, Malod, Guillaume, Srinivasan, Srikanth: Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput. 44(5), 1173–1201 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2014). Approaching the Chasm at Depth Four. J. ACM 61(6), 33:1–33:16

  • Rohit Gurjar, Arpita Korwar & Nitin Saxena (2016). Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. In 31st Conference on Computational Complexity, CCC 2016, 29:1–29:16

  • Gurjar, Rohit, Korwar, Arpita, Saxena, Nitin, Thierauf, Thomas: Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Computational Complexity 26(4), 835–880 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  • Hrubeš, Pavel, Wigderson, Avi, Yehudayoff, Amir: Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society 24(3), 871–898 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  • Laurent Hyafil (1977). The Power of Commutativity. In FOCS, 171–174

  • Mark Jerrum & Marc Snir: Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM 29(3), 874–897 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  • Kayal, Neeraj, Limaye, Nutan, Saha, Chandan, Srinivasan, Srikanth: An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. In 55th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2014, 61–70 (2014)

    Google Scholar 

  • Kayal, Neeraj, Saha, Chandan, Saptharishi, Ramprasad: A super-polynomial lower bound for regular arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, 146–153 (2014)

    MATH  Google Scholar 

  • Mrinal Kumar & Shubhangi Saraf: On the Power of Homogeneous Depth 4 Arithmetic Circuits. In 55th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2014, 364–373 (2014)

    Google Scholar 

  • Guillaume Lagarde, Nutan Limaye & Srikanth Srinivasan (2017). Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, 41:1–41:14

  • Lagarde, Guillaume, Malod, Guillaume, Perifel, Sylvain: Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC) 23, 94 (2016)

    MATH  Google Scholar 

  • Limaye, Nutan, Malod, Guillaume, Srinivasan, Srikanth: Lower Bounds for Non-Commutative Skew Circuits. Theory of Computing 12(1), 1–38 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  • Guillaume Malod & Natacha Portier: Characterizing Valiant's algebraic complexity classes. J. Complexity 24(1), 16–38 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Noam Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In STOC, 410–418

  • Noam Nisan & Avi Wigderson: Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3), 217–234 (1997)

    MathSciNet  MATH  Google Scholar 

  • Ran Raz (2009). Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2), 8:1–8:17

  • Ran Raz & Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1), 1–19 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Ran Raz & Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity 18(2), 171–207 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Ramprasad Saptharishi & Anamay Tengse: Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees. Electronic Colloquium on Computational Complexity (ECCC) 24, 135 (2017)

    Google Scholar 

  • Saxena, Nitin: Progress on Polynomial Identity Testing. Bulletin of the EATCS 99, 49–79 (2009)

    MathSciNet  MATH  Google Scholar 

  • Saxena, Nitin: Progress on Polynomial Identity Testing - II. Electronic Colloquium on Computational Complexity (ECCC) 20, 186 (2013)

    Google Scholar 

  • Amir Shpilka & Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1), 1–27 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Amir Shpilka & 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)

    MathSciNet  MATH  Google Scholar 

  • Leslie G. Valiant, Sven Skyum, S. Berkowitz & Charles Rackoff (1983). Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput. 12(4), 641–644.

Download references

Acknowledgments

We thank the anonymous reviewers of Computational Complexity for their many suggestions that helped improve the quality of the exposition. Many open questions in Section 7 were suggested by one of the reviewers. An extended abstract of this paper appeared in Lagarde et al. (2017).

Author information

Authors and Affiliations

  1. IRIF, Université Paris-Diderot, Paris, France

    Guillaume Lagarde

  2. Department of Computer Science and Engineering, IIT Bombay, Mumbai, India

    Nutan Limaye

  3. Department of Mathematics, IIT Bombay, Mumbai, India

    Srikanth Srinivasan

Authors
  1. Guillaume Lagarde
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nutan Limaye
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Srikanth Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nutan Limaye.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lagarde, G., Limaye, N. & Srinivasan, S. Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees. comput. complex. 28, 471–542 (2019). https://doi.org/10.1007/s00037-018-0171-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-018-0171-9

Keywords

Subject classification

Search

Navigation