Document Open Access Logo

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

Authors Pranjal Dutta , Prateek Dwivedi , Nitin Saxena

PDF

File

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

Document Identifiers

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

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 ∧.

Cite As Get 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

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.

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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact