Nitin Saxena

According to our database, Nitin Saxena authored at least 67 papers between 2004 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits.

C. S. Bhargav, Sagnik Dutta, Nitin Saxena

ACM Trans. Comput. Theory, December, 2024

Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP.

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

Comput. Complex., June, 2024

How Easy Is It to Describe Hard Polynomials?: Technical Perspective.

Nitin Saxena

Commun. ACM, February, 2024

Solving polynomial systems over non-fields and applications to modular polynomial factoring.

Sayak Chakrabarti, Ashish Dwivedi, Nitin Saxena

J. Symb. Comput., 2024

Lower Bounds for the Sum of Small-Size Algebraic Branching Programs.

C. S. Bhargav, Prateek Dwivedi, Nitin Saxena

Proceedings of the Theory and Applications of Models of Computation, 2024

Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring.

C. S. Bhargav, Prateek Dwivedi, Nitin Saxena

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme.

Anindya Ganguly, Angshuman Karmakar, Nitin Saxena

IACR Cryptol. ePrint Arch., 2023

Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q.

Rishabh Batra, Nitin Saxena, Devansh Shringi

Comput. Complex., 2023

An effective description of the roots of bivariates mod pk and the related Igusa's local zeta function.

Sayak Chakrabarti, Nitin Saxena

Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

2022

Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials.

Pranav Bisht, Nitin Saxena

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits.

Pranjal Dutta, Nitin Saxena

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Efficiently factoring polynomials modulo <i>p</i>⁴.

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

J. Symb. Comput., 2021

Blackbox identity testing for sum of special ROABPs and its border class.

Pranav Bisht, Nitin Saxena

Comput. Complex., 2021

A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization.

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Demystifying the border of depth-3 algebraic circuits.

Pranjal Dutta, Prateek Dwivedi, Nitin Saxena

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

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

Pranjal Dutta, Prateek Dwivedi, Nitin Saxena

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Computing Igusa's local zeta function of univariates in deterministic polynomial-time.

Ashish Dwivedi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2020

Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT.

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2020

Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs.

Pranav Bisht, Nitin Saxena

Electron. Colloquium Comput. Complex., 2020

Special-case algorithms for blackbox radical membership, nullstellensatz and transcendence degree.

Abhibhav Garg, Nitin Saxena

Proceedings of the ISSAC '20: International Symposium on Symbolic and Algebraic Computation, 2020

2019

Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field.

Zeyu Guo, Nitin Saxena, Amit Sinhababu

Theory Comput., 2019

Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications.

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Electron. Colloquium Comput. Complex., 2019

Efficiently factoring polynomials modulo $p^4$.

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Electron. Colloquium Comput. Complex., 2019

Efficiently factoring polynomials modulo p⁴.

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

CoRR, 2019

Research in theoretical computer science.

Meena Mahajan, Madhavan Mukund, Nitin Saxena

Commun. ACM, 2019

Efficiently Factoring Polynomials Modulo p4.

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019

2018

Algebraic dependencies and PSPACE algorithms in approximative complexity.

Zeyu Guo, Nitin Saxena, Amit Sinhababu

Electron. Colloquium Comput. Complex., 2018

Towards blackbox identity testing of log-variate circuits.

Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

Electron. Colloquium Comput. Complex., 2018

Bootstrapping variables in algebraic circuits.

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Electron. Colloquium Comput. Complex., 2018

Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits.

Anurag Pandey, Nitin Saxena, Amit Sinhababu

Comput. Complex., 2018

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields.

Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski

Algorithmica, 2018

2017

Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs.

Rohit Gurjar, Arpita Korwar, Nitin Saxena

Theory Comput., 2017

Discovering the roots: Uniform closure results for algebraic classes under factoring.

Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Electron. Colloquium Comput. Complex., 2017

Irreducibility and deterministic r-th root finding over finite fields.

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Electron. Colloquium Comput. Complex., 2017

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.

Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena

Electron. Colloquium Comput. Complex., 2017

Irreducibility and r-th root finding over finite fields.

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

CoRR, 2017

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs.

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

Comput. Complex., 2017

2016

Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits.

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

SIAM J. Comput., 2016

Identity Testing for constant-width, and commutative, read-once oblivious ABPs.

Rohit Gurjar, Arpita Korwar, Nitin Saxena

Electron. Colloquium Comput. Complex., 2016

Integer Factoring Using Small Algebraic Dependencies.

Manindra Agrawal, Nitin Saxena, Shubham Sahai Srivastava

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits.

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

SIAM J. Comput., 2015

2014

Deterministic polynomial factoring and association schemes.

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

LMS J. Comput. Math., 2014

Deterministic Identity Testing for Sum of Read Once ABPs.

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

Electron. Colloquium Comput. Complex., 2014

2013

From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits.

Nitin Saxena, C. Seshadhri

J. ACM, 2013

Progress on Polynomial Identity Testing - II.

Nitin Saxena

Electron. Colloquium Comput. Complex., 2013

Hitting-sets for low-distance multilinear depth-3.

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Electron. Colloquium Comput. Complex., 2013

A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Comput. Complex., 2013

Quasi-polynomial hitting-set for set-depth-Δ formulas.

Manindra Agrawal, Chandan Saha, Nitin Saxena

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter.

Nitin Saxena, C. Seshadhri

SIAM J. Comput., 2012

Trading GRH for algebra: Algorithms for factoring polynomials and related structures.

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

Math. Comput., 2012

Algebraic Independence in Positive Characteristic - A p-Adic Calculus.

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

Electron. Colloquium Comput. Complex., 2012

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas.

Manindra Agrawal, Chandan Saha, Nitin Saxena

Electron. Colloquium Comput. Complex., 2012

2011

An Almost Optimal Rank Bound for Depth-3 Identities.

Nitin Saxena, C. Seshadhri

SIAM J. Comput., 2011

Algebraic Independence and Blackbox Identity Testing.

Malte Beecken, Johannes Mittmann, Nitin Saxena

Electron. Colloquium Comput. Complex., 2011

Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2011

2010

Deterministic Polynomial Time Algorithms for Matrix Completion Problems.

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

SIAM J. Comput., 2010

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.

Nitin Saxena, C. Seshadhri

Electron. Colloquium Comput. Complex., 2010

2009

Progress on Polynomial Identity Testing.

Nitin Saxena

Electron. Colloquium Comput. Complex., 2009

The Power of Depth 2 Circuits over Algebras.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2009

2008

Schemes for Deterministic Polynomial Factoring.

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Electron. Colloquium Comput. Complex., 2008

2007

Diagonal Circuit Identity Testing and Lower Bounds.

Nitin Saxena

Electron. Colloquium Comput. Complex., 2007

Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Nitin Saxena

Comput. Complex., 2007

2006

Complexity of Ring Morphism Problems.

Neeraj Kayal, Nitin Saxena

Comput. Complex., 2006

Equivalence of F-Algebras and Cubic Forms.

Manindra Agrawal, Nitin Saxena

Proceedings of the STACS 2006, 2006

2005

Automorphisms of Finite Rings and Applications to Complexity of Problems.

Manindra Agrawal, Nitin Saxena

Proceedings of the STACS 2005, 2005

On the Ring Isomorphism and Automorphism Problems.

Neeraj Kayal, Nitin Saxena

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

On the Ring Isomorphism & Automorphism Problems

Neeraj Kayal, Nitin Saxena

Electron. Colloquium Comput. Complex., 2004