Document Open Access Logo

Hardness Amplification for Non-Commutative Arithmetic Circuits

Authors Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.12.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Marco L. Carmosino
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Russell Impagliazzo
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Shachar Lovett
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Ivan Mihajlin
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA

Funding

  • Carmosino, Marco L.: Supported by the Simons Foundation
  • Impagliazzo, Russell: Supported by the Simons Foundation
  • Lovett, Shachar: Supported by NSF CAREER award 1350481 and CCF award 1614023
  • Mihajlin, Ivan: Supported by the Simons Foundation

Cite As Get BibTex

Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CCC.2018.12

Abstract

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.
This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • arithmetic circuits
  • hardness amplification
  • circuit lower bounds
  • non-commutative computation

Metrics

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

References

  1. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 67-75. IEEE Computer Society, 2008. Google Scholar
  2. Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja. Randomized polynomial time identity testing for noncommutative circuits. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 831-841. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055442.
  3. Vikraman Arvind, Pushkar S. Joglekar, and S. Raja. Noncommutative valiant’s classes: Structure and complete problems. TOCT, 9(1):3:1-3:29, 2016. URL: http://dx.doi.org/10.1145/2956230.
  4. Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 677-686. ACM, 2010. Google Scholar
  5. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical computer science, 22(3):317-330, 1983. Google Scholar
  6. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. Electronic Colloquium on Computational Complexity (ECCC), 24:27, 2017. Google Scholar
  7. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 653-664. ACM, 2017. Google Scholar
  8. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 24:9, 2017. Google Scholar
  9. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. Google Scholar
  10. Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Relationless completeness and separations. Electronic Colloquium on Computational Complexity (ECCC), 17:40, 2010. URL: http://eccc.hpi-web.de/report/2010/040.
  11. Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871-898, 2011. Google Scholar
  12. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. Google Scholar
  13. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303. ACM, 2014. Google Scholar
  14. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410-418. ACM, 1991. Google Scholar
  15. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  16. Amir Shpilka, Amir Yehudayoff, et al. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trendsregistered in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  17. Leslie G. Valiant. Completeness classes in algebra. In Michael J. Fischer, Richard A. DeMillo, Nancy A. Lynch, Walter A. Burkhard, and Alfred V. Aho, editors, Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261. ACM, 1979. URL: http://dx.doi.org/10.1145/800135.804419.
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