Document Open Access Logo

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

Authors Nikhil Gupta, Chandan Saha, Bhargav Thankey

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.23.pdf
  • Filesize: 0.85 MB
  • 31 pages

Document Identifiers

Author Details

Nikhil Gupta
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
Chandan Saha
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
Bhargav Thankey
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

Acknowledgements

We would like to thank Neeraj Kayal and Ankit Garg for sitting through a presentation of this work and giving us useful feedback. Thanks specially to Ankit for bringing the work of Chen and Tell [Lijie Chen and Roei Tell, 2019] to our notice. A part of this work is done at Microsoft Research India (MSRI), where CS is spending a sabbatical year. CS would like to thank MSRI for providing an excellent research environment and for the hospitality.

Cite AsGet BibTex

Nikhil Gupta, Chandan Saha, and Bhargav Thankey. A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 23:1-23:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.23

Abstract

We show an Ω̃(n^2.5) lower bound for general depth four arithmetic circuits computing an explicit n-variate degree-Θ(n) multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey [Amir Shpilka and Amir Yehudayoff, 2010], no super-quadratic lower bound was known for depth four circuits over fields of characteristic ≠ 2 before this work. The previous best lower bound is Ω̃(n^1.5) [Abhijat Sharma, 2017], which is a slight quantitative improvement over the roughly Ω(n^1.33) bound obtained by invoking the super-linear lower bound for constant depth circuits in [Ran Raz, 2010; Victor Shoup and Roman Smolensky, 1997]. Our lower bound proof follows the approach of the almost cubic lower bound for depth three circuits in [Neeraj Kayal et al., 2016] by replacing the shifted partials measure with a suitable variant of the projected shifted partials measure, but it differs from [Neeraj Kayal et al., 2016]’s proof at a crucial step - namely, the way "heavy" product gates are handled. Loosely speaking, a heavy product gate has a relatively high fan-in. Product gates of a depth three circuit compute products of affine forms, and so, it is easy to prune Θ(n) many heavy product gates by projecting the circuit to a low-dimensional affine subspace [Neeraj Kayal et al., 2016; Amir Shpilka and Avi Wigderson, 2001]. However, in a depth four circuit, the second (from the top) layer of product gates compute products of polynomials having arbitrary degree, and hence it was not clear how to prune such heavy product gates from the circuit. We show that heavy product gates can also be eliminated from a depth four circuit by projecting the circuit to a low-dimensional affine subspace, unless the heavy gates together account for Ω̃(n^2.5) size. This part of our argument is inspired by a well-known greedy approximation algorithm for the weighted set-cover problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • depth four arithmetic circuits
  • Projected Shifted Partials
  • super-quadratic lower bound

Metrics

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

References

  1. Manindra Agrawal, Eric Allender, and Samir Datta. On TC^0, AC^0, and Arithmetic Circuits. J. Comput. Syst. Sci., 60(2):395-421, 2000. Conference version appeared in the proceedings of CCC 1997. 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 and Depth-3 Transcendence Degree-k Circuits. SIAM J. Comput., 45(4):1533-1562, 2016. Conference version appeared in the proceedings of STOC 2012. Google Scholar
  3. 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
  4. Miklós Ajtai. Σ¹₁-Formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  5. Boris Alexeev, Michael A. Forbes, and Jacob Tsimerman. Tensor rank: Some lower and upper bounds. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 283-291. IEEE Computer Society, 2011. Google Scholar
  6. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Conference version appeared in the proceedings of CCC 2008. Google Scholar
  7. Noga Alon and Ravi B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1-22, 1987. Google Scholar
  8. Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  9. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. TOCT, 10(1):3:1-3:30, 2018. Conference version appeared in the proceedings of CCC 2016. Google Scholar
  10. A. E. Andreev. On a method for obtaining more than quadratic effective lower bounds for thecomplexity of π-schemes. Moscow Univ. Math. Bull., 42:63-66, 1987. Google Scholar
  11. Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. Computational Complexity, 27(1):1-29, 2018. Conference version appeared in the proceedings of STOC 2010. Google Scholar
  12. Nikhil Balaji, Nutan Limaye, and Srikanth Srinivasan. An almost cubic lower bound for ΣΠΣ circuits computing a polynomial in VP. Electronic Colloquium on Computational Complexity (ECCC), 23:143, 2016. URL: http://eccc.hpi-web.de/report/2016/143.
  13. Walter Baur and Volker Strassen. The Complexity of Partial Derivatives. Theor. Comput. Sci., 22:317-330, 1983. Google Scholar
  14. Norbert Blum. A Boolean Function Requiring 3n Network Size. Theor. Comput. Sci., 28:337-345, 1984. URL: https://doi.org/10.1016/0304-3975(83)90029-4.
  15. Allan Borodin, Alexander A. Razborov, and Roman Smolensky. On Lower Bounds for Read-K-Times Branching Programs. Computational Complexity, 3:1-18, 1993. Google Scholar
  16. Peter Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and computation in mathematics. Springer, 2000. Google Scholar
  17. Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997. Google Scholar
  18. Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 12:1-12:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  19. Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. Electronic Colloquium on Computational Complexity (ECCC), page 170, 2019. URL: https://eccc.weizmann.ac.il/report/2019/170.
  20. Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits "just beyond" known lower bounds. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 34-41. ACM, 2019. Google Scholar
  21. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1-138, 2011. Google Scholar
  22. Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 934-945. IEEE Computer Society, 2018. Google Scholar
  23. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications. SIAM J. Comput., 48(1):70-92, 2019. Conference version appeared in the proceedings of STOC 2001. Google Scholar
  24. Danny Dolev, Cynthia Dwork, Nicholas Pippenger, and Avi Wigderson. Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 42-51. ACM, 1983. Google Scholar
  25. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 615-624. ACM, 2012. Google Scholar
  26. Paul Erdős. Beweis eines Satzes von Tschebyschef. Acta Litt. Sci. Szeged, 5:194-198, January 1932. Google Scholar
  27. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 89-98. IEEE Computer Society, 2016. Google Scholar
  28. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput., 44(5):1173-1201, 2015. Conference version appeared in the proceedings of STOC 2014. Google Scholar
  29. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Conference version appeared in the proceedings of FOCS 1981. Google Scholar
  30. Michelangelo Grigni and Michael Sipser. Monotone Separation of Logarithmic Space from Logarithmic Depth. J. Comput. Syst. Sci., 50(3):433-437, 1995. Conference version appeared in the proceedings of CCC 1991. Google Scholar
  31. 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, Dallas, Texas, USA, May 23-26, 1998, pages 577-582, 1998. Google Scholar
  32. Dima Grigoriev and Alexander 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. Conference version appeared in the proceedings of FOCS 1998. Google Scholar
  33. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the Chasm at Depth Four. J. ACM, 61(6):33:1-33:16, 2014. Conference version appeared in the proceedings of CCC 2013. Google Scholar
  34. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic Circuits: A Chasm at Depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. Conference version appeared in the proceedings of FOCS 2013. Google Scholar
  35. Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20, 1986. Google Scholar
  36. Johan Håstad. The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. Conference version appeared in the proceedings of FOCS 1993. Google Scholar
  37. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. Conference version appeared in the proceedings of CCC 2001. Google Scholar
  38. Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 667-676. ACM, 2010. Google Scholar
  39. Pavel Hrubes and Amir Yehudayoff. Arithmetic complexity in ring extensions. Theory of Computing, 7(1):119-129, 2011. Google Scholar
  40. Pavel Hrubes and Amir Yehudayoff. On Isoperimetric Profiles and Computational Complexity. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 89:1-89:12, 2016. Google Scholar
  41. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput., 26(3):693-707, 1997. Conference version appeared in the proceedings of STOC 1993. Google Scholar
  42. Kazuo Iwama and Hiroki Morizumi. An Explicit Lower Bound of 5n - o(n) for Boolean Circuits. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, volume 2420 of Lecture Notes in Computer Science, pages 353-364. Springer, 2002. Google Scholar
  43. Mark Jerrum and Marc Snir. Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM, 29(3):874-897, 1982. Google Scholar
  44. K. Kalorkoti. A Lower Bound for the Formula Size of Rational Functions. SIAM J. Comput., 14(3):678-687, 1985. Google Scholar
  45. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 633-643, 2016. Google Scholar
  46. Mauricio Karchmer and Avi Wigderson. Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math., 3(2):255-265, 1990. Conference version appeared in the proceedings of STOC 1988. Google Scholar
  47. Mauricio Karchmer and Avi Wigderson. On Span Programs. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993, pages 102-111. IEEE Computer Society, 1993. Google Scholar
  48. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19:81, 2012. URL: http://eccc.hpi-web.de/report/2012/081.
  49. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput., 46(1):307-335, 2017. Conference version appeared in the proceedings of FOCS 2014. Google Scholar
  50. Neeraj Kayal and Chandan Saha. Lower Bounds for Sums of Products of Low arity Polynomials. Electronic Colloquium on Computational Complexity (ECCC), 22:73, 2015. URL: http://eccc.hpi-web.de/report/2015/073.
  51. Neeraj Kayal and Chandan Saha. Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. Computational Complexity, 25(2):419-454, 2016. Conference version appeared in the proceedings of CCC 2015. Google Scholar
  52. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 146-153, 2014. Google Scholar
  53. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 33:1-33:15, 2016. Google Scholar
  54. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. Google Scholar
  55. Alexander S. Kulikov, Olga Melanich, and Ivan Mihajlin. A 5n - o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function. In S. Barry Cooper, Anuj Dawar, and Benedikt Löwe, editors, How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings, volume 7318 of Lecture Notes in Computer Science, pages 432-439. Springer, 2012. Google Scholar
  56. Mrinal Kumar and Shubhangi Saraf. Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 751-762, 2014. Google Scholar
  57. Mrinal Kumar and Shubhangi Saraf. Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 35:1-35:29, 2016. Google Scholar
  58. Mrinal Kumar and Shubhangi Saraf. On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM J. Comput., 46(1):336-387, 2017. Conference version appeared in the proceedings of FOCS 2014. Google Scholar
  59. Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. Electronic Colloquium on Computational Complexity (ECCC), 26:47, 2019. Google Scholar
  60. Oded Lachish and Ran Raz. Explicit lower bound of 4.5n - o(n) for boolean circuits. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 399-408. ACM, 2001. Google Scholar
  61. Shachar Lovett. Computing polynomials with few multiplications. Theory of Computing, 7(1):185-188, 2011. Google Scholar
  62. Jacques Morgenstern. Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform. J. ACM, 20(2):305-306, 1973. Google Scholar
  63. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 890-901, 2018. Google Scholar
  64. E. I. Nechiporuk. On a Boolean function. Doklady of the Academy of Sciences of the USSR, 164(4):765-766, 1966. Google Scholar
  65. Noam Nisan. Lower Bounds for Non-Commutative Computation (Extended Abstract). In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418. ACM, 1991. Google Scholar
  66. Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity, 6(3):217-234, 1997. Conference version appeared in the proceedings of FOCS 1995. Google Scholar
  67. Igor Carboni Oliveira and Rahul Santhanam. Hardness Magnification for Natural Problems. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 65-76. IEEE Computer Society, 2018. Google Scholar
  68. Pavel Pudlák. Communication in Bounded Depth Circuits. Combinatorica, 14(2):203-216, 1994. Google Scholar
  69. Pavel Pudlák. A note on the use of determinant for proving lower bounds on the size of linear circuits. Inf. Process. Lett., 74(5-6):197-201, 2000. Google Scholar
  70. Ran Raz. On the Complexity of Matrix Product. SIAM J. Comput., 32(5):1356-1369, 2003. Conference version appeared in the proceedings of STOC 2002. Google Scholar
  71. Ran Raz. Separation of Multilinear Circuit and Formula Size. Theory of Computing, 2(6):121-135, 2006. Conference version appeared in the proceedings of FOCS 2004. Google Scholar
  72. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1-8:17, 2009. Conference version appeared in the proceedings of STOC 2004. Google Scholar
  73. Ran Raz. Elusive Functions and Lower Bounds for Arithmetic Circuits. Theory of Computing, 6(1):135-177, 2010. Conference version appeared in the proceedings of STOC 2008. Google Scholar
  74. Ran Raz. Tensor-Rank and Lower Bounds for Arithmetic Formulas. J. ACM, 60(6):40:1-40:15, 2013. Conference version appeared in the proceedings of STOC 2010. Google Scholar
  75. Ran Raz and Pierre McKenzie. Separation of the Monotone NC Hierarchy. Combinatorica, 19(3):403-435, 1999. Conference version appeared in the proceedings of FOCS 1997. Google Scholar
  76. Ran Raz and Amir Shpilka. Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput., 32(2):488-513, 2003. Conference version appeared in the proceedings of STOC 2001. Google Scholar
  77. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM J. Comput., 38(4):1624-1647, 2008. Conference version appeared in the proceedings of FOCS 2007. Google Scholar
  78. Ran Raz and Amir Yehudayoff. Balancing Syntactically Multilinear Arithmetic Circuits. Computational Complexity, 17(4):515-535, 2008. Google Scholar
  79. Ran Raz and Amir Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171-207, 2009. Conference version appeared in the proceedings of CCC 2008. Google Scholar
  80. A. A. Razborov. Lower bounds on monotone complexity of the logical permanent. Mathematical notes of the Academy of Sciences of the USSR, 37(6):485-493, June 1985. Google Scholar
  81. Alexander A. Razborov. Lower bounds on the monotone complexity of some Boolean functions. Soviet Mathematics Doklady, 31:354-357, 1985. Google Scholar
  82. John H. Reif and Stephen R. Tate. On Threshold Circuits and Polynomial Computation. SIAM J. Comput., 21(5):896-908, 1992. Google Scholar
  83. Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential Lower Bounds for Monotone Span Programs. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406-415. IEEE Computer Society, 2016. Google Scholar
  84. Eli Shamir and Marc Snir. Lower bounds on the number of multiplications and the number of additions in monotone computations. Technical report, IBM RC 6757, 1977. Google Scholar
  85. Abhijat Sharma. An Improved Lower Bound for Depth Four Arithmetic Circuits. Master’s thesis, Indian Institute of Science, Bangalore, India, 2017. Google Scholar
  86. Victor Shoup and Roman Smolensky. Lower Bounds for Polynomial Evaluation and Interpolation Problems. Computational Complexity, 6(4):301-311, 1997. Conference version appeared in the proceedings of FOCS 1991. Google Scholar
  87. Amir Shpilka and Avi Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001. Conference version appeared in the proceedings of CCC 1999. Google Scholar
  88. Amir Shpilka and 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. Google Scholar
  89. Srikanth Srinivasan. Strongly Exponential Separation Between Monotone VP and Monotone VNP. Electronic Colloquium on Computational Complexity (ECCC), 26:32, 2019. Google Scholar
  90. Volker Strassen. Die berechnungskomplexiät von elementarysymmetrischen funktionen und von iterpolationskoeffizienten. Numerische Mathematik, 20:238-251, 1973. Google Scholar
  91. Volker Strassen. Vermeidung von divisionen. The Journal für die Reine und Angewandte Mathematik, 264:182-202, 1973. Google Scholar
  92. Éva Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141-142, 1988. Google Scholar
  93. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. Conference version appeared in the proceedings of MFCS 2013. Google Scholar
  94. Leslie G. Valiant. On Non-linear Lower Bounds in Computational Complexity. In William C. Rounds, Nancy Martin, Jack W. Carlyle, and Michael A. Harrison, editors, Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA, pages 45-53. ACM, 1975. Google Scholar
  95. Leslie G. Valiant. Graph-Theoretic Arguments in Low-Level Complexity. In Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, pages 162-176, 1977. Google Scholar
  96. Leslie G. Valiant. Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261, 1979. Google Scholar
  97. Leslie G. Valiant. Negation can be exponentially powerful. Theor. Comput. Sci., 12:303-314, 1980. Conference version appeared in the proceedings of STOC 1979. Google Scholar
  98. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput., 12(4):641-644, 1983. Google Scholar
  99. Vijay V. Vazirani. Approximation algorithms. Springer, 2001. URL: http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-65367-7.
  100. Joachim von zur Gathen and Gadiel Seroussi. Boolean Circuits Versus Arithmetic Circuits. Inf. Comput., 91(1):142-154, 1991. Google Scholar
  101. Ryan Williams. Nonuniform ACC Circuit Lower Bounds. J. ACM, 61(1):2:1-2:32, 2014. Conference version appeared in the proceedings of CCC 2011. Google Scholar
  102. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.
  103. Morris Yau. Almost cubic bound for depth three circuits in VP. Electronic Colloquium on Computational Complexity (ECCC), 23:187, 2016. URL: http://eccc.hpi-web.de/report/2016/187.
  104. Amir Yehudayoff. Separating monotone VP and VNP. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 425-429. ACM, 2019. 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 Imprint Privacy Contact