Document Open Access Logo

Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

Authors Pranjal Dutta , Prateek Dwivedi , Nitin Saxena

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.11.pdf
  • Filesize: 1.04 MB
  • 27 pages

Document Identifiers

Author Details

Pranjal Dutta
  • Chennai Mathematical Institute, India
  • Department of Computer Science & Engineering, IIT Kanpur, India
Prateek Dwivedi
  • Department of Computer Science & Engineering, IIT Kanpur, India
Nitin Saxena
  • Department of Computer Science & Engineering, IIT Kanpur, India

Funding

  • Dutta, Pranjal: Google Ph. D. Fellowship
  • Saxena, Nitin: DST (DST/SJF/MSA-01/2013-14) and N. Rama Rao Chair

Acknowledgements

Pranjal thanks CSE, IIT Kanpur for the hospitality.

Cite AsGet BibTex

Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 11:1-11:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.11

Abstract

Polynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth-4 reduction (Agrawal & Vinay, FOCS'08) has made PIT for depth-4 circuits, an enticing pursuit. The largely open special-cases of sum-product-of-sum-of-univariates (Σ^[k] Π Σ ∧) and sum-product-of-constant-degree-polynomials (Σ^[k] Π Σ Π^[δ]), for constants k, δ, have been a source of many great ideas in the last two decades. For eg. depth-3 ideas (Dvir & Shpilka, STOC'05; Kayal & Saxena, CCC'06; Saxena & Seshadhri, FOCS'10, STOC'11); depth-4 ideas (Beecken, Mittmann & Saxena, ICALP'11; Saha,Saxena & Saptharishi, Comput.Compl.'13; Forbes, FOCS'15; Kumar & Saraf, CCC'16); geometric Sylvester-Gallai ideas (Kayal & Saraf, FOCS'09; Shpilka, STOC'19; Peleg & Shpilka, CCC'20, STOC'21). We solve two of the basic underlying open problems in this work. We give the first polynomial-time PIT for Σ^[k] Π Σ ∧. Further, we give the first quasipolynomial time blackbox PIT for both Σ^[k] Π Σ ∧ and Σ^[k] Π Σ Π^[δ]. No subexponential time algorithm was known prior to this work (even if k = δ = 3). A key technical ingredient in all the three algorithms is how the logarithmic derivative, and its power-series, modify the top Π-gate to ∧.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Polynomial identity testing
  • hitting set
  • depth-4 circuits

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 International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 92-105. Springer, 2005. URL: https://doi.org/10.1007/11590156_6.
  2. Manindra Agrawal, Sumanta Ghosh, and Nitin Saxena. Bootstrapping variables in algebraic circuits. Proceedings of the National Academy of Sciences, 116(17):8107-8118, 2019. Preliminary version in Symposium on Theory of Computing, 2018 (STOC'18). URL: https://doi.org/10.1073/pnas.1901272116.
  3. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. URL: https://doi.org/10.1137/140975103.
  4. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of mathematics, pages 781-793, 2004. URL: https://annals.math.princeton.edu/2004/160-2/p12.
  5. 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 Journal on Computing, 45(4):1533-1562, 2016. Preliminary version in 44^th Symposium on Theory of Computing, 2018 (STOC'12). URL: https://doi.org/10.1137/130910725.
  6. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In Proceedings of the 45^th Annual ACM symposium on Theory of computing (STOC'13), pages 321-330, 2013. URL: https://doi.org/10.1145/2488608.2488649.
  7. Manindra Agrawal and V Vinay. Arithmetic Circuits: A Chasm at Depth Four. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 67-75. IEEE, 2008. URL: https://ieeexplore.ieee.org/document/4690941.
  8. 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. ACM Transactions on Computation Theory (TOCT), 10(1):1-30, 2018. Preliminary version in the IEEE 31^st Computational Complexity Conference (CCC'16). URL: https://doi.org/10.1145/3170709.
  9. Robert Andrews. Algebraic Hardness Versus Randomness in Low Characteristic. In 35th Computational Complexity Conference (CCC 2020), volume 169 of LIPIcs, pages 37:1-37:32. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.37.
  10. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  11. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM (JACM), 45(1):70-122, 1998. Preliminary version in 33^rd Annual Symposium on Foundations of Computer Science (FOCS'92). URL: https://doi.org/10.1145/273865.273901.
  12. Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Information and Computation, 222:2-19, 2013. Preliminary version in 38^th International Colloquium on Automata, Languages and Programming (ICALP'11). URL: https://www.sciencedirect.com/science/article/pii/S0890540112001435.
  13. Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the 20^th Annual ACM symposium on Theory of computing (STOC'88), pages 301-309, 1988. URL: https://doi.org/10.1145/62212.62241.
  14. Pranav Bisht and Nitin Saxena. Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs. Computational Complexity, 2021. URL: https://cse.iitk.ac.in/users/nitin/papers/constWidth-log-var.pdf.
  15. Enrico Carlini, Maria Virginia Catalisano, and Anthony V. Geramita. The solution to the Waring problem for monomials and the sum of coprime monomials. Journal of Algebra, 370:5-14, 2012. URL: https://doi.org/10.1016/j.jalgebra.2012.07.028.
  16. Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, and Anamay Tengse. On the Existence of Algebraically Natural Proofs. In IEEE 61^st Annual Symposium on Foundations of Computer Science (FOCS'20), 2020. URL: https://eccc.weizmann.ac.il/report/2020/063/.
  17. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs randomness for bounded depth arithmetic circuits. In 33^rd Computational Complexity Conference (CCC'18). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.13.
  18. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://www.sciencedirect.com/science/article/abs/pii/0020019078900674.
  19. Pranjal Dutta, Nitin Saxena, and Amit Sinhababu. Discovering the roots: Uniform closure results for algebraic classes under factoring. In Proceedings of the 50^th Annual ACM SIGACT Symposium on Theory of Computing (STOC'18), pages 1152-1165, 2018. URL: https://doi.org/10.1145/3188745.3188760.
  20. Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:21. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.23.
  21. Zeev Dvir, Rafael Mendes De Oliveira, and Amir Shpilka. Testing equivalence of polynomials under shifts. In International Colloquium on Automata, Languages, and Programming, pages 417-428. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_35.
  22. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM Journal on Computing, 36(5):1404-1434, 2007. URL: https://doi.org/10.1137/05063605X.
  23. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing, 39(4):1279-1293, 2010. Preliminary version in Proceedings of the 40^th Annual ACM symposium on Theory of computing (STOC'08). URL: https://doi.org/10.1137/080735850.
  24. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. SIAM Journal on Computing, 62(3):109-115, 2019. Preliminary version in Proceedings of the 48^th Annual ACM symposium on Theory of Computing (STOC'16). URL: https://epubs.siam.org/doi/abs/10.1137/16M1097870?journalCode=smjcat.
  25. Michael A Forbes. Deterministic divisibility testing via shifted partial derivatives. In Proceedings of the 56^th Annual Symposium on Foundations of Computer Science (FOCS'15), pages 451-465. IEEE, 2015. URL: https://ieeexplore.ieee.org/document/7354409/.
  26. Michael A Forbes, Sumanta Ghosh, and Nitin Saxena. Towards blackbox identity testing of log-variate circuits. In 45^th International Colloquium on Automata, Languages, and Programming (ICALP'18). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.54.
  27. Michael A Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46^th Annual ACM symposium on Theory of computing (STOC'14), pages 867-875, 2014. URL: https://doi.org/10.1145/2591796.2591816.
  28. Michael A Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54^th Annual Symposium on Foundations of Computer Science (FOCS'13), pages 243-252, 2013. URL: https://ieeexplore.ieee.org/document/6686160/.
  29. Michael A Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Theory of Computing, 14:1-45, 2018. Preliminary version in Proceedings of the 49^th Annual ACM SIGACT Symposium on Theory of Computing (STOC'19). URL: https://theoryofcomputing.org/articles/v014a018/.
  30. Abhibhav Garg and Nitin Saxena. Special-case algorithms for blackbox radical membership, Nullstellensatz and transcendence degree. In Proceedings of the 45^th International Symposium on Symbolic and Algebraic Computation, pages 186-193, 2020. Google Scholar
  31. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. In 57^th Annual Symposium on Foundations of Computer Science (FOCS'16), pages 109-117. IEEE, 2016. URL: https://ieeexplore.ieee.org/document/7782923.
  32. Joshua A Grochow. Unifying known lower bounds via geometric complexity theory. Computational Complexity, 24(2):393-475, 2015. Preliminary version in the IEEE 29th Computational Complexity Conference (CCC'14). URL: https://doi.org/10.1007/s00037-015-0103-x.
  33. Zeyu Guo. Variety Evasive Subspace Families. In 36th Computational Complexity Conference (CCC 2021). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://zeyuguo.bitbucket.io/papers/chow.pdf.
  34. Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon. Derandomization from Algebraic Hardness: Treading the Borders. In 60^th IEEE Annual Symposium on Foundations of Computer Science (FOCS'19), pages 147-157. IEEE Computer Society, 2019. URL: https://ieeexplore.ieee.org/document/8948610/.
  35. Ankit Gupta. Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. In Electronic Colloquium on Computational Complexity (ECCC), volume 21, page 130, 2014. URL: https://eccc.weizmann.ac.il/report/2014/130/.
  36. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. SIAM Journal on Computing, 45(3):1064-1079, 2016. 54^th Annual Symposium on Foundations of Computer Science (FOCS'13). URL: https://doi.org/10.1137/140957123.
  37. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs. Theory of Computing, 13(2):1-21, 2017. Preliminary version in the 31^st Computational Complexity Conference (CCC'16). URL: https://doi.org/10.4086/toc.2017.v013a002.
  38. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Computational Complexity, 26(4):835-880, 2017. Preliminary version in the IEEE 30^th Computational Complexity Conference (CCC'15). URL: https://doi.org/10.1007/s00037-016-0141-z.
  39. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute. In Proceedings of the 12^th annual ACM symposium on Theory of computing (STOC'80), pages 262-272, 1980. URL: https://doi.org/10.1145/800141.804674.
  40. Maurice Jansen, Youming Qiao, and Jayalal Sarma. Deterministic Black-Box Identity Testing π-Ordered Algebraic Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, volume 8 of LIPIcs, pages 296-307. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.296.
  41. A Grochow Joshua, D Mulmuley Ketan, and Qiao Youming. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 34:1-34:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.34.
  42. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Preliminary version in the Proceedings of the 35^th Annual ACM symposium on Theory of computing (STOC'03). URL: https://doi.org/10.1007/s00037-004-0182-6.
  43. Zohar S Karnin, Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM Journal on Computing, 42(6):2114-2131, 2013. Preliminary version in the Proceedings of the 42^nd ACM symposium on Theory of computing (STOC'10). URL: https://doi.org/10.1137/110824516?af=R.
  44. Zohar S Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In 24^th Annual IEEE Conference on Computational Complexity (CCC'09), pages 274-285. IEEE, 2009. URL: https://ieeexplore.ieee.org/document/5231339.
  45. Zohar S Karnin and Amir Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333, 2011. Preliminary version in the 23^rd Annual IEEE Conference on Computational Complexity (CCC'08). URL: https://doi.org/10.1007/s00493-011-2537-3.
  46. Neeraj Kayal, Pascal Koiran, Timothée Pecatte, and Chandan Saha. Lower bounds for sums of powers of low degree univariates. In International Colloquium on Automata, Languages, and Programming (ICALP'15), pages 810-821. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_66.
  47. Neeraj Kayal and Nitin Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 16(2):115-138, 2007. Preliminary version in the 21^st Computational Complexity Conference (CCC'06). URL: https://doi.org/10.1007/s00037-007-0226-9.
  48. Adam Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory of computing, 2(1):185-206, 2006. Preliminary version in the 16^th Annual Conference on Learning Theory (COLT'03). URL: https://theoryofcomputing.org/articles/v002a010/.
  49. Adam R Klivans and Daniel Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33^rd Annual ACM symposium on Theory of computing (STOC'01), pages 216-223, 2001. URL: https://doi.org/10.1145/380752.380801.
  50. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. URL: https://www.sciencedirect.com/science/article/pii/S0304397512003131.
  51. Pascal Koiran, Natacha Portier, and Sébastien Tavenas. A Wronskian approach to the real τ-conjecture. Journal of Symbolic Computation, 68:195-214, 2015. URL: https://www.sciencedirect.com/science/article/pii/S0747717114001047.
  52. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In IEEE 29^th Conference on Computational Complexity (CCC'14), pages 169-180. IEEE, 2014. URL: https://ieeexplore.ieee.org/document/6875486.
  53. Mrinal Kumar, C Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP is hard, then so are equations for it. Preprint avilable at https://arxiv.org/abs/2012.07056, 2020.
  54. Mrinal Kumar and Ramprasad Saptharishi. Hardness-randomness tradeoffs for algebraic computation. Bulletin of EATCS, 3(129), 2019. URL: https://mrinalkr.bitbucket.io/papers/hardness-randomness-survey.pdf.
  55. Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse. Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. In Proceedings of the 30^th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 639-646, 2019. URL: https://doi.org/10.5555/3310435.3310475.
  56. Mrinal Kumar and Shubhangi Saraf. Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In 31^st Conference on Computational Complexity, CCC 2016, volume 50 of LIPIcs, pages 35:1-35:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.35.
  57. Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. Theory Comput., 13(1):1-33, 2017. Preliminary version in the 31^st Conference on Computational Complexity (CCC'16). URL: http://www.theoryofcomputing.org/articles/v013a006/.
  58. Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Chic. J. Theor. Comput. Sci., 2:1-19, 2019. URL: http://cjtcs.cs.uchicago.edu/articles/2019/2/cj19-02.pdf.
  59. László Lovász. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory (FCT'79), volume 79, pages 565-574, 1979. URL: http://www.math.uwaterloo.ca/~harvey/W11/1979-Lovasz-OnDeterminantsMatchingsAndRandomAlgs.pdf.
  60. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM (JACM), 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  61. Partha Mukhopadhyay. Depth-4 identity testing and Noether’s normalization lemma. In International Computer Science Symposium in Russia (CSR'16), pages 309-323. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-34171-2_22.
  62. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Comb., 7(1):105-113, 1987. Preliminary version in the Proceedings of the 19^th Annual ACM symposium on Theory of Computing (STOC'87). URL: https://doi.org/10.1007/BF02579206.
  63. Ketan D Mulmuley. Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma. In IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS'12), pages 629-638. IEEE, 2012. URL: http://arxiv.org/abs/1209.5993.
  64. Ketan D Mulmuley. The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98-107, 2012. URL: https://doi.org/10.1145/2184319.2184341.
  65. Ivan Niven. Formal power series. The American Mathematical Monthly, 76(8):871-889, 1969. URL: http://www.jstor.org/stable/2317940.
  66. Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  67. Anurag Pandey, Nitin Saxena, and Amit Sinhababu. Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Computational Complexity, 27(4):617-670, 2018. Preliminary version in the 41^st International Symposium on Mathematical Foundations of Computer Science (MFCS'16). URL: https://doi.org/10.1007/s00037-018-0167-5.
  68. Shir Peleg and Amir Shpilka. A generalized Sylvester-Gallai type theorem for quadratic polynomials. In 35^th Computational Complexity Conference (CCC'20). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.8.
  69. Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testing algorithm for ∑^[3] ∏∑∏^[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials. In 53^rd Annual ACM symposium on Theory of computing (STOC'21), 2021. URL: http://arxiv.org/abs/2006.08263.
  70. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. Preliminary version in the 19^th IEEE Annual Conference on Computational Complexity (CCC'04). URL: https://doi.org/10.1007/s00037-005-0188-8.
  71. Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. A case of depth-3 identity testing, sparse factorization and duality. Computational Complexity, 22(1):39-69, 2013. URL: https://doi.org/10.1007/s00037-012-0054-4.
  72. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2019. URL: https://github.com/dasarpmar/lowerbounds-survey/releases.
  73. Ramprasad Saptharishi. Private communication, 2019. Google Scholar
  74. Shubhangi Saraf and Ilya Volkovich. Black-box identity testing of depth-4 multilinear circuits. Combinatorica, 38(5):1205-1238, 2018. Preliminary version in the Proceedings of the 43^rd Annual ACM symposium on Theory of computing (STOC'11). URL: https://doi.org/10.1007/s00493-016-3460-4.
  75. Nitin Saxena. Diagonal circuit identity testing and lower bounds. In International Colloquium on Automata, Languages, and Programming (ICALP'08), pages 60-71. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_6.
  76. Nitin Saxena. Progress on Polynomial Identity Testing. Bulletin of the EATCS, 99:49-79, 2009. URL: https://www.cse.iitk.ac.in/users/nitin/papers/pit-survey09.pdf.
  77. Nitin Saxena. Progress on polynomial identity testing-II. In Perspectives in Computational Complexity, pages 131-146. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-05446-9_7.
  78. Nitin Saxena and Comandur Seshadhri. An almost optimal rank bound for depth-3 identities. SIAM journal on computing, 40(1):200-224, 2011. Preliminary version in the 24^th IEEE Conference on Computational Complexity (CCC'09). URL: https://doi.org/10.1137/090770679.
  79. Nitin Saxena and Comandur 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. Preliminary version in the 43^rd Annual ACM symposium on Theory of computing (STOC'11). URL: https://doi.org/10.1137/10848232.
  80. Nitin Saxena and Comandur Seshadhri. From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. Journal of the ACM (JACM), 60(5):1-33, 2013. Preliminary version in the 51^st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10). URL: https://doi.org/10.1145/2528403.
  81. Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  82. Adi Shamir. IP= PSPACE. Journal of the ACM (JACM), 39(4):869-877, 1992. URL: https://doi.org/10.1145/146585.146609.
  83. Amir Shpilka. Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM Journal on Computing, 38(6):2130-2161, 2009. Preliminary version in the Proceedings of the 39^th Annual ACM symposium on Theory of Computing (STOC 2007). URL: https://doi.org/10.1137/070694879.
  84. Amir Shpilka. Sylvester-Gallai type theorems for quadratic polynomials. In Proceedings of the 51^st Annual ACM SIGACT Symposium on Theory of Computing (STOC'19), pages 1203-1214, 2019. URL: https://doi.org/10.1145/3313276.3316341.
  85. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010. URL: https://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf.
  86. Amit Kumar Sinhababu. Power series in complexity: Algebraic Dependence, Factor Conjecture and Hitting Set for Closure of VP. PhD thesis, PhD thesis, Indian Institute of Technology Kanpur, 2019. URL: https://www.cse.iitk.ac.in/users/nitin/theses/sinhababu-2019.pdf.
  87. Leslie G Valiant. Completeness classes in algebra. In Proceedings of the 11^th Annual ACM symposium on Theory of computing (STOC'79), pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
  88. Wolmer Vasconcelos. Computational methods in commutative algebra and algebraic geometry, volume 2. Springer Science & Business Media, 2004. URL: https://www.springer.com/gp/book/9783540213116.
  89. Richard Zippel. Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM '79, pages 216-226, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
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