Deterministic Identity Testing Paradigms for Bounded Top-fanin Depth-4 Circuits
by Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena
Theory of Computing, Volume 22(2175), pp. 1-38, 2026
Bibliography with links to cited articles
[1] Manindra Agrawal: Proving lower bounds via pseudo-random generators. In International Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 2005. [doi: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. [doi: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. [doi:10.1137/140975103]
[4] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena: Primes is in P. Annals of mathematics, 2004. [doi:10.4007/annals.2004.160.781]
[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, 2016. Preliminary version in 44th Symposium on Theory of Computing, 2018 (STOC’12). [doi:10.1137/130910725]
[6] Manindra Agrawal, Chandan Saha, and Nitin Saxena:
Quasi-polynomial hitting-set for set-depth-
formulas. In Symposium
on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA,
June 1-4, 2013, pp. 321–330. ACM, 2013. [doi:10.1145/2488608.2488649]
[7] Manindra Agrawal and V. Vinay: Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008, pp. 67–75. IEEE Computer Society, 2008. [doi:10.1109/FOCS.2008.32]
[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, 10(1):3:1–3:30, 2018. [doi:10.1145/3170709]
[9] Robert Andrews: Algebraic hardness versus randomness in low characteristic. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, Saarbrücken, Germany (Virtual Conference), July 28-31, 2020, volume 169 of LIPIcs, pp. 37:1–37:32. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. [doi: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), 1998. [doi:10.1145/278298.278306]
[11] Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM (JACM), 1998. Preliminary version in 33rd Annual Symposium on Foundations of Computer Science (FOCS’92). [doi:10.1145/273865.273901]
[12] Malte Beecken, Johannes Mittmann, and Nitin Saxena: Algebraic independence and blackbox identity testing. Information and Computation, 2013. Preliminary version in 38th International Colloquium on Automata, Languages and Programming (ICALP’11). [doi:10.1016/j.ic.2012.10.004]
[13] Michael Ben-Or and Prasoon Tiwari: A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the 20th Annual ACM symposium on Theory of computing (STOC’88), 1988. [doi:10.1145/62212.62241]
[14] Pranav Bisht and Nitin Saxena: Blackbox identity testing for sum of special roabps and its border class. Computational Complexity, 30(1):8, 2021. [doi:10.1007/S00037-021-00209-Y]
[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, 2012. [doi: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 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 870–880. IEEE, 2020. [doi:10.1109/FOCS46700.2020.00085]
[17] Suryajith Chillara, Coral Grichener, and Amir Shpilka: On hardness of testing equivalence to sparse polynomials under shifts. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, Hamburg, Germany, March 7-9, 2023, volume 254 of LIPIcs, pp. 22:1–22:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [doi:10.4230/LIPICS.STACS.2023.22]
[18] Chi-Ning Chou, Mrinal Kumar, and Noam Solomon: Hardness vs randomness for bounded depth arithmetic circuits. In 33rd Computational Complexity Conference, CCC 2018, San Diego, CA, USA, June 22-24, 2018, volume 102 of LIPIcs, pp. 13:1–13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. [doi:10.4230/LIPICS.CCC.2018.13]
[19] Richard A. DeMillo and Richard J. Lipton: A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4]
[20] Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena: Demystifying the border of depth-3 algebraic circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pp. 92–103. IEEE, 2021. [doi:10.1109/FOCS52979.2021.00018]
[21] 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, Toronto, Ontario, Canada (Virtual Conference), July 20-23, 2021, volume 200 of LIPIcs, pp. 11:1–11:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. [doi:10.4230/LIPICS.CCC.2021.11]
[22] Pranjal Dutta and Sumanta Ghosh: Advances in polynomial identity testing. ACM SIGACT News, 55(2):53–88, 2024. [doi:10.1145/3674159.3674165]
[23] Pranjal Dutta and Nitin Saxena: Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pp. 200–211. IEEE, 2022. [doi:10.1109/FOCS54457.2022.00026]
[24] Pranjal Dutta, Nitin Saxena, and Amit Sinhababu: Discovering the roots: Uniform closure results for algebraic classes under factoring. Journal of the ACM, 69(3):Art. 18, 39, 2022. [doi:10.1145/3510359]
[25] Pranjal Dutta, Nitin Saxena, and Thomas Thierauf: Weighted
sum-of-squares lower bounds for univariate polynomials imply VP
q
VNP. Computational Complexity, 33(1):3, 2024. Preliminary version
in 12th Innovations in Theoretical Computer Science Conference (ITCS
2021). [doi:10.1007/S00037-024-00249-0]
[26] Zeev Dvir and Amir Shpilka: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM Journal on Computing, 2007. [doi:10.1137/05063605X]
[27] Zeev Dvir, Amir Shpilka, and Amir Yehudayoff: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM Journal on Computing, 39(4):1279–1293, 2009. [doi:10.1137/080735850]
[28] Stephen Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect matching is in quasi-NC. SIAM Journal on Computing, 2019. Preliminary version in Proceedings of the 48th Annual ACM symposium on Theory of Computing (STOC’16). [doi:10.1137/16M1097870]
[29] Michael A. Forbes: Deterministic divisibility testing via shifted partial derivatives. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pp. 451–465. IEEE Computer Soc., Los Alamitos, CA, 2015. [doi:10.1109/FOCS.2015.35]
[30] Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena: Towards blackbox identity testing of log-variate circuits. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, volume 107 of LIPIcs, pp. 54:1–54:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. [doi:10.4230/LIPICS.ICALP.2018.54]
[31] Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka: Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 867–875. ACM, 2014. [doi:10.1145/2591796.2591816]
[32] Michael A. Forbes and Amir Shpilka: 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, Berkeley, CA, USA, October, 26-29, 2013, pp. 243–252. IEEE Computer Society, 2013. [doi:10.1109/FOCS.2013.34]
[33] 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):1–45, 2018. [doi:10.4086/TOC.2018.V014A018]
[34] Michael Andrew Forbes: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph. D. thesis, Massachusetts Institute of Technology, 2014.
[35] Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta: Robust radical sylvester-gallai theorem for quadratics. In 38th International Symposium on Computational Geometry, SoCG 2022, Berlin, Germany, June 7-10, 2022, volume 224 of LIPIcs, pp. 42:1–42:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [doi:10.4230/LIPICS.SOCG.2022.42]
[36] Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta: Rank bounds and PIT for depth-4 circuits with top fan-in 3 and constant bottom fan-in via a non-linear edelstein-kelly theorem. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pp. 2143–2169. IEEE, 2025. [doi:10.1109/FOCS63196.2025.00114]
[37] Abhibhav Garg and Nitin Saxena: Special-case algorithms for blackbox radical membership, Nullstellensatz and transcendence degree. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, pp. 186–193. ACM, 2020. [doi:10.1145/3373207.3404030]
[38] Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson: A deterministic polynomial time algorithm for non-commutative rational identity testing. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016, pp. 109–117. IEEE Computer Society, 2016. [doi:10.1109/FOCS.2016.95]
[39] Joshua A. Grochow: Unifying known lower bounds via geometric complexity theory. Computational Complexity, 24(2):393–475, 2015. [doi:10.1007/S00037-015-0103-X]
[40] Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao: Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, volume 55 of LIPIcs, pp. 34:1–34:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. [doi:10.4230/LIPICS.ICALP.2016.34]
[41] Zeyu Guo: Variety evasive subspace families. Computational Complexity, 33(2):10, 2024. [doi:10.1007/S00037-024-00256-1]
[42] Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon: Derandomization from algebraic hardness. SIAM Journal on Computing, 51(2):315–335, 2022. [doi:10.1137/20M1347395]
[43] Zeyu Guo and Siki Wang: Deterministic depth-4 PIT and normalization. CoRR, abs/2504.15143, 2025. [doi:10.48550/ARXIV.2504.15143, arXiv:2504.15143]
[44] Ankit Gupta: Algebraic geometric techniques for depth-4 PIT & sylvester-gallai conjectures for varieties. Electronic Colloquium on Computational Complexity, TR14-130, 2014. [arXiv:TR14-130]
[45] Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi: Arithmetic circuits: A chasm at depth 3. SIAM Journal on Computing, 45(3):1064–1079, 2016. [doi:10.1137/140957123]
[46] 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(1):1–21, 2017. [doi:10.4086/TOC.2017.V013A002]
[47] 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. [doi:10.1007/S00037-016-0141-Z]
[48] Joos Heintz and Claus-Peter Schnorr: Testing polynomials which are easy to compute. In Proceedings of the 12th annual ACM symposium on Theory of computing (STOC’80), 1980. [doi:10.1145/800141.804674]
[49] Maurice J. Jansen, Youming Qiao, and Jayalal Sarma: Deterministic black-box identity testing $pi$-ordered algebraic branching programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, Chennai, India, December 15-18, 2010, volume 8 of LIPIcs, pp. 296–307. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. [doi:10.4230/LIPICS.FSTTCS.2010.296]
[50] Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1–46, 2004. [doi:10.1007/s00037-004-0182-6]
[51] 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, 2013. Preliminary version in the Proceedings of the 42nd ACM symposium on Theory of computing (STOC’10). [doi:10.1137/110824516]
[52] Zohar S Karnin and Amir Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 2011. Preliminary version in the 23rd Annual IEEE Conference on Computational Complexity (CCC’08). [doi:10.1007/s00493-011-2537-3]
[53] Zohar Shay Karnin and Amir Shpilka: Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 274–285. IEEE Computer Society, 2009. [doi:10.1109/CCC.2009.18]
[54] Neeraj Kayal, Pascal Koiran, Timothée Pecatte, and Chandan Saha: Lower bounds for sums of powers of low degree univariates. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pp. 810–821. Springer, 2015. [doi:10.1007/978-3-662-47672-7_66]
[55] Neeraj Kayal and Nitin Saxena: Polynomial identity testing for depth 3 circuits. Computational Complexity, 2007. Preliminary version in the 21st Computational Complexity Conference (CCC’06). [doi:10.1007/s00037-007-0226-9]
[56] Adam R. Klivans and Amir Shpilka: Learning restricted models of arithmetic circuits. Theory of Computing, 2(10):185–206, 2006. [doi:10.4086/TOC.2006.V002A010]
[57] Adam R Klivans and Daniel Spielman: Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM symposium on Theory of computing (STOC’01), 2001. [doi:10.1145/380752.380801]
[58] Pascal Koiran: Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 2012. [doi:10.1016/j.tcs.2012.03.041]
[59] Pascal Koiran, Natacha Portier, and Sébastien Tavenas: A wronskian approach to the real τ-conjecture. Journal of Symbolic Computation, 68:195–214, 2015. [doi:10.1016/j.jsc.2014.09.036]
[60] Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka: Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pp. 169–180. IEEE Computer Society, 2014. [doi:10.1109/CCC.2014.25]
[61] Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse: If VNP is hard, then so are equations for it. In 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, Marseille, France (Virtual Conference), March 15-18, 2022, volume 219 of LIPIcs, pp. 44:1–44:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [doi:10.4230/LIPICS.STACS.2022.44]
[62] Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse: Near-optimal bootstrapping of hitting sets for algebraic models. Theory of Computing, 19:1–30, 2023. [doi:10.4086/TOC.2023.V019A012]
[63] 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, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.35]
[64] Mrinal Kumar and Shubhangi Saraf: Arithmetic circuits with locally low algebraic rank. Theory of Computing, 13(1):1–33, 2017. [doi:10.4086/TOC.2017.V013A006]
[65] Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel: Non-commutative computations: lower bounds and polynomial identity testing. Chicago Journal of Theoretical Computer Science, 2019, 2019. [doi:10.4086/cjtcs.2019.002]
[66] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas: Superpolynomial lower bounds against low-depth algebraic circuits. Journal of the ACM, 72(4):26:1–26:35, 2025. [doi:10.1145/3734215]
[67] László Lovász: On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory (FCT’79), 1979.
[68] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. Journal of the ACM (JACM), 1992. [doi:10.1145/146585.146605]
[69] Meena Mahajan: Algebraic complexity classes. In Perspectives in Computational Complexity, volume 26 of Progr. Comput. Sci. Appl. Logic, pp. 51–75. Birkhäuser/Springer, Cham, 2014. [doi:10.1007/978-3-319-05446-9_4]
[70] Partha Mukhopadhyay: Depth-4 identity testing and noether’s normalization lemma. In Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings, volume 9691 of Lecture Notes in Computer Science, pp. 309–323. Springer, 2016. [doi:10.1007/978-3-319-34171-2_22]
[71] Ketan Mulmuley: Geometric complexity theory V: equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 629–638. IEEE Computer Society, 2012. [doi:10.1109/FOCS.2012.15]
[72] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani: Matching is as easy as matrix inversion. Combinatorica, 1987. Preliminary version in the Proceedings of the 19th Annual ACM symposium on Theory of Computing (STOC’87). [doi:10.1007/BF02579206]
[73] Ketan D. Mulmuley: The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98–107, 2012. [doi:10.1145/2184319.2184341]
[74] Ivan Niven: Formal power series. The American Mathematical Monthly, 1969. [doi:10.2307/2317940]
[75] Rafael Oliveira and Akash Kumar Sengupta: Radical sylvester-gallai theorem for cubics. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pp. 212–220. IEEE, 2022. [doi:10.1109/FOCS54457.2022.00027]
[76] Øystein Ore: Über höhere kongruenzen. Norsk Matematisk Forenings Skrifter, 1922.
[77] 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. [doi:10.1007/S00037-018-0167-5]
[78] Shir Peleg and Amir Shpilka: A generalized sylvester-gallai type theorem for quadratic polynomials. In 35th Computational Complexity Conference, CCC 2020, Saarbrücken, Germany (Virtual Conference), July 28-31, 2020, volume 169 of LIPIcs, pp. 8:1–8:33. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. [doi:10.4230/LIPICS.CCC.2020.8]
[79] Shir Peleg and Amir Shpilka: Polynomial time deterministic identity testing algorithm for ∑ [3] ∏ ∑ ∏ [2] circuits via edelstein-kelly type theorem for quadratic polynomials. In 53rd Annual ACM symposium on Theory of computing (STOC’21), 2021. [doi:10.1145/3406325.3451013]
[80] Ran Raz and Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1–19, 2005. [doi:10.1007/s00037-005-0188-8]
[81] 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. [doi:10.1007/s00037-012-0054-4]
[82] Ramprasad Saptharishi: Unified Approaches to Polynomial Identity Testing and Lower Bounds. Ph. D. thesis, PhD thesis, Chennai Mathematical Institute, 2013.
[83] Ramprasad Saptharishi: Private communication, 2019.
[84] Ramprasad Saptharishi: A survey of lower bounds in arithmetic circuit complexity. 2021.
[85] Shubhangi Saraf and Ilya Volkovich: Black-box identity testing of depth-4 multilinear circuits. Combinatorica, 38(5):1205–1238, 2018. [doi:10.1007/S00493-016-3460-4]
[86] Nitin Saxena: Diagonal circuit identity testing and lower bounds. In International Colloquium on Automata, Languages, and Programming (ICALP’08), pp. 60–71. Springer, 2008. [doi:10.1007/978-3-540-70575-8_6]
[87] Nitin Saxena: Progress on polynomial identity testing. Bulletin of the European Association for Theoretical Computer Science, (99):49–79, 2009.
[88] Nitin Saxena: Progress on polynomial identity testing-ii. In Perspectives in Computational Complexity. Springer, 2014. [doi:10.1007/978-3-319-05446-9_7]
[89] Nitin Saxena and Comandur Seshadhri: An almost optimal rank bound for depth-3 identities. SIAM journal on computing, 2011. Preliminary version in the 24th IEEE Conference on Computational Complexity (CCC’09). [doi:10.1137/090770679]
[90] Nitin Saxena and Comandur Seshadhri: Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn’t matter. SIAM Journal on Computing, 2012. Preliminary version in the 43rd Annual ACM symposium on Theory of computing (STOC’11). [doi:10.1137/10848232]
[91] 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), 2013. Preliminary version in the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). [doi:10.1145/2528403]
[92] J. T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225]
[93] Adi Shamir: IP= PSPACE. Journal of the ACM (JACM), 1992. [doi:10.1145/146585.146609]
[94] Amir Shpilka: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM Journal on Computing, 38(6):2130–2161, 2009. [doi:10.1137/070694879]
[95] Amir Shpilka: Sylvester-gallai type theorems for quadratic polynomials. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 1203–1214. ACM, 2019. [doi:10.1145/3313276.3316341]
[96] Amir Shpilka and Yann Tal: Polynomial identity testing and reconstruction for depth-4 powering circuits of high degree. Electronic Colloquium on Computational Complexity, TR26-029, 2026. [arXiv:TR26-029]
[97] 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), 2010. [doi:10.1561/0400000039]
[98] Amit Sinhababu: Power series in complexity: Algebraic Dependence, Factor Conjecture and Hitting Set for Closure of VP. Ph. D. thesis, Indian Institute of Technology Kanpur, 2019.
[99] Leslie G Valiant: Completeness classes in algebra. In Proceedings of the 11th Annual ACM symposium on Theory of computing (STOC’79), 1979. [doi:10.1145/800135.804419]
[100] Wolmer Vasconcelos: Computational methods in commutative algebra and algebraic geometry. 2004.
[101] Richard Zippel: Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM ’79, 1979. [doi:10.1007/3-540-09519-5_73]
