Browse by Fellow

Dwivedi, Ashish ; Mittal, Rajat ; Saxena, Nitin (2021) Efficiently factoring polynomials modulo p⁴ Journal of Symbolic Computation, 104 . pp. 805-823. ISSN 0747-7171

Dutta, Pranjal ; Saxena, Nitin ; Thierauf, Thomas (2021) A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization In: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Dagstuhl, Germany.

Dwivedi, Ashish ; Saxena, Nitin (2020) Computing Igusa’s local zeta function of univariates in deterministic polynomial-time In: 14th Biannual Algorithmic Number Theory Symposium, ANTS-XIV.

Garg, Abhibhav ; Saxena, Nitin (2020) Special-case algorithms for blackbox radical membership, nullstellensatz and transcendence degree In: ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, July 2020.

Guo, Zeyu ; Saxena, Nitin ; Sinhababu, Amit (2019) Algebraic Dependencies And Pspace Algorithms In Approximative Complexity Over Any Field Theory of Computing, 15 (1). pp. 1-30. ISSN 1557-2862

Agrawal, Manindra ; Ghosh, Sumanta ; Saxena, Nitin (2019) Bootstrapping variables in algebraic circuits Proceedings of the National Academy of Sciences of the United States of America, 116 (17). pp. 8107-8118. ISSN 0027-8424

Dwivedi, Ashish ; Mittal, Rajat ; Saxena, Nitin (2019) Counting Basic-Irreducible Factors Mod pk in Deterministic Poly-Time and p-Adic Applications In: 34th Computational Complexity Conference (CCC 2019), Dagstuhl, Germany.

Dwivedi, Ashish ; Mittal, Rajat ; Saxena, Nitin (2019) Efficiently factoring polynomials modulo p⁴ Association for Computing Machinery.

Mahajan, Meena ; Mukund, Madhavan ; Saxena, Nitin (2019) Research in theoretical computer science Communications of the ACM, 62 (11). pp. 92-95. ISSN 0001-0782

Guo, Zeyu ; Saxena, Nitin ; Sinhababu, Amit (2018) Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity In: 33rd Computational Complexity Conference (CCC 2018), Dagstuhl, Germany.

Pandey, Anurag ; Saxena, Nitin ; Sinhababu, Amit (2018) Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits Computational Complexity, 27 (4). pp. 617-670. ISSN 1016-3328

Agrawal, Manindra ; Ghosh, Sumanta ; Saxena, Nitin (2018) Bootstrapping variables in algebraic circuits In: STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, June 2018.

Dutta, Pranjal ; Saxena, Nitin ; Sinhababu, Amit (2018) Discovering the roots: uniform closure results for algebraic classes under factoring In: STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, June 2018.

Forbes, Michael A. ; Ghosh, Sumanta ; Saxena, Nitin (2018) Towards Blackbox Identity Testing of Log-Variate Circuits In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Dagstuhl, Germany.

Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin ; Thierauf, Thomas (2017) Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs Computational Complexity, 26 (4). pp. 835-880. ISSN 1016-3328

Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin (2017) Identity Testing For Constant-width, And Any-order, Read-once Oblivious Arithmetic Branching Programs Theory of Computing, 13 (1). pp. 1-21. ISSN 1557-2862

Bhargava, Vishwas ; Ivanyos, Gábor ; Mittal, Rajat ; Saxena, Nitin (2017) Irreducibility and Deterministic r-th Root Finding over Finite Fields In: ISSAC '17: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, July 2017.

Pandey, Anurag ; Saxena, Nitin ; Sinhababu, Amit (2016) Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Dagstuhl, Germany.

Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin (2016) Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs In: 31st Conference on Computational Complexity (CCC 2016).

Agrawal, Manindra ; Saxena, Nitin ; Srivastava, Shubham Sahai (2016) Integer Factoring Using Small Algebraic Dependencies In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).

Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin ; Thierauf, Thomas (2015) Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs Schloss Dagstuhl--Leibniz-Zentrum für Informatik.

Agrawal, Manindra ; Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin (2015) Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits SIAM Journal on Computing, 44 (3). pp. 669-697. ISSN 0097-5397

Ivanyos, Gabor ; Karpinski, Marek ; Santha, Miklos ; Saxena, Nitin ; Shparlinski, Igor (2015) Polynomial Interpolation and Identity Testing from High Powers over Finite Fields Algorithmica, 80 . pp. 560-575. ISSN 0178-4617

MITTMANN, JOHANNES ; SAXENA, NITIN ; SCHEIBLECHNER, PETER (2014) Algebraic Independence In Positive Characteristic: A p-adic Calculus Transactions of the American Mathematical Society, 366 (7). pp. 3425-3450. ISSN 0002-9947

Arora, Manuel ; Ivanyos, Gábor ; Karpinski, Marek ; Saxena, Nitin (2014) Deterministic polynomial factoring and association schemes LMS Journal of Computation and Mathematics, 17 (1). pp. 123-140. ISSN 1461-1570

Saxena, Nitin (2014) Progress on Polynomial Identity Testing - II Progress in Computer Science and Applied Logic, 26 (1). Springer Nature Switzerland AG. ISBN 978-3-319-05446-9

Saha, Chandan ; Saptharishi, Ramprasad ; Saxena, Nitin (2013) A Case of Depth-3 Identity Testing, Sparse Factorization and Duality Computational Complexity, 22 (1). pp. 39-69. ISSN 1016-3328

Saxena, Nitin ; Seshadhri, C. (2013) From sylvester-gallai configurations to rank bounds Journal of the ACM, 60 (5). pp. 1-33. ISSN 0004-5411

Agrawal, Manindra ; Saha, Chandan ; Saxena, Nitin (2013) Quasi-polynomial hitting-set for set-depth-Δ formulas In: STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, June 2013.

Saxena, Nitin ; Seshadhri, C. (2012) Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter SIAM Journal on Computing, 41 (5). pp. 1285-1298. ISSN 0097-5397

Agrawal, Manindra ; Saha, Chandan ; Saptharishi, Ramprasad ; Saxena, Nitin (2012) Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits In: STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, May 2012, New York, USA.

Ivanyos, Gábor ; Karpinski, Marek ; Rónyai, Lajos ; Saxena, Nitin (2012) Trading GRH for algebra: Algorithms for factoring polynomials and related structures Mathematics of computation, 81 (277). pp. 493-531. ISSN 0025-5718

Beecken, Malte ; Mittmann, Johannes ; Saxena, Nitin (2011) Algebraic Independence and Blackbox Identity Testing In: Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, July 2011.

Beecken, Malte ; Mittmann, Johannes ; Saxena, Nitin (2011) Algebraic Independence and Blackbox Identity Testing Part of the Lecture Notes in Computer Science, 6756 . Springer Nature Switzerland AG, Springer, Berlin, Heidelberg. ISBN 978-3-642-22012-8

Saxena, Nitin ; Seshadhri, C. (2011) An Almost Optimal Rank Bound for Depth-3 Identities SIAM Journal on Computing, 40 (1). pp. 200-224. ISSN 0097-5397

Saxena, Nitin ; Seshadhri, C. (2011) Blackbox identity testing for bounded top fanin depth-3 circuits In: STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing, June 2011.

Agrawal, Manindra ; Saha, Chandan ; Saptharishi, Ramprasad ; Saxena, Nitin (2011) Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits In: STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, May 2012, New York, USA.

Ivanyos, Gábor ; Karpinski, Marek ; Saxena, Nitin (2010) Deterministic Polynomial Time Algorithms for Matrix Completion Problems SIAM Journal on Computing, 39 (8). pp. 3736-3751. ISSN 0097-5397

Saxena, Nitin ; Seshadhri, C. (2010) From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits In: FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, October 2010.

Saxena, Nitin ; Seshadhri, C. (2009) An Almost Optimal Rank Bound for Depth-3 Identities In: CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, July 2009.

Saha, Chandan ; Saptharishi, Ramprasad ; Saxena, Nitin (2009) The Power of Depth 2 Circuits over Algebras In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science.

Saxena, Nitin (2009) Progress on Polynomial Identity Testing Bulletin of the European Association for Theoretical Computer Science . pp. 49-79. ISSN 1433-8092

Ivanyos, Gábor ; Karpinski, Marek ; Saxena, Nitin (2009) Schemes for deterministic polynomial factoring In: ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 2009.

Saxena, Nitin (2008) Diagonal Circuit Identity Testing and Lower Bounds In: Automata, Languages and Programming. Part of the Lecture Notes in Computer Science book series (LNCS, volume 5125), 5125 . Springer Nature Switzerland AG, Springer, Berlin, Heidelberg, pp. 60-71.

SAXENA, NITIN ; SEVERINI, SIMONE ; SHPARLINSKI, IGOR E. (2007) Parameters Of Integral Circulant Graphs And Periodic Quantum Dynamics International Journal of Quantum Information, 05 (03). pp. 417-430. ISSN 0219-7499

Kayal, Neeraj ; Saxena, Nitin (2007) Polynomial Identity Testing for Depth 3 Circuits Computational Complexity, 16 (2). pp. 115-138. ISSN 1016-3328

Kayal, Neeraj ; Saxena, Nitin (2006) Complexity of Ring Morphism Problems Computational Complexity, 15 . pp. 342-390. ISSN 1016-3328

Agrawal, Manindra ; Saxena, Nitin (2006) Equivalence of F -Algebras and Cubic Forms In: STACS 2006. Part of the Lecture Notes in Computer Science book series (LNCS, volume 3884), 3884 . Springer Nature Switzerland AG, Springer, Berlin, Heidelberg, pp. 115-126. ISBN 978-3-540-32288-7

Kayal, N. ; Saxena, N. (2006) Polynomial Identity Testing for Depth 3 Circuits In: CCC '06: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, July 2006.

Agrawal, Manindra ; Saxena, Nitin (2005) Automorphisms of Finite Rings and Applications to Complexity of Problems In: Annual Symposium on Theoretical Aspects of Computer Science.

Kayal, N. ; Saxena, N. (2005) On the Ring Isomorphism and Automorphism Problems In: CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, June 2005.

Agrawal, Manindra ; Kayal, Neeraj ; Saxena, Nitin (2004) PRIMES is in P Annals of Mathematics, 160 (2). pp. 781-793. ISSN 0003-486X