Nitin Saxena

ORCID

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 60

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Comput. Complex.

Computational Complexity Conference

Publications

Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP. Comput. Complex. 33 (1) (2024)
Nitin Saxena
How Easy Is It to Describe Hard Polynomials?: Technical Perspective. Commun. ACM 67 (2) (2024)
Sayak Chakrabarti, Ashish Dwivedi, Nitin Saxena
Solving polynomial systems over non-fields and applications to modular polynomial factoring. J. Symb. Comput. 125 (2024)
C. S. Bhargav, Prateek Dwivedi, Nitin Saxena
Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring. STOC (2024)
C. S. Bhargav, Prateek Dwivedi, Nitin Saxena
Lower Bounds for the Sum of Small-Size Algebraic Branching Programs. TAMC (2024)
Rishabh Batra, Nitin Saxena, Devansh Shringi
Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q. Comput. Complex. 32 (1) (2023)
Sayak Chakrabarti, Nitin Saxena
An effective description of the roots of bivariates mod pk and the related Igusa's local zeta function. ISSAC (2023)
Anindya Ganguly, Angshuman Karmakar, Nitin Saxena
VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme. IACR Cryptol. ePrint Arch. 2023 (2023)
Anindya Ganguly, Angshuman Karmakar, Nitin Saxena
VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme. CoRR (2023)
Anindya Ganguly, Angshuman Karmakar, Nitin Saxena
VDOO: A Short, Fast, Post-quantum Multivariate Digital Signature Scheme. INDOCRYPT (2) (2023)
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits. CoRR (2023)
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Demystifying the border of depth-3 algebraic circuits. FOCS (2022)
Pranjal Dutta, Nitin Saxena
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. FOCS (2022)
C. S. Bhargav, Sagnik Dutta, Nitin Saxena
Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits. MFCS (2022)
Pranav Bisht, Nitin Saxena
Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials. FSTTCS (2022)
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring. J. ACM 69 (3) (2022)
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Demystifying the border of depth-3 algebraic circuits. FOCS (2021)
Pranav Bisht, Nitin Saxena
Blackbox identity testing for sum of special ROABPs and its border class. Comput. Complex. 30 (1) (2021)
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. ITCS (2021)
Pranjal Dutta, Prateek Dwivedi, Nitin Saxena
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. Computational Complexity Conference (2021)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
. J. Symb. Comput. 104 (2021)
Abhibhav Garg, Nitin Saxena
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree. CoRR (2020)
Ashish Dwivedi, Nitin Saxena
Computing Igusa's local zeta function of univariates in deterministic polynomial-time. CoRR (2020)
Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT. Electron. Colloquium Comput. Complex. 27 (2020)
Abhibhav Garg, Nitin Saxena
Special-case algorithms for blackbox radical membership, nullstellensatz and transcendence degree. ISSAC (2020)
Ashish Dwivedi, Nitin Saxena
Computing Igusa's local zeta function of univariates in deterministic polynomial-time. Electron. Colloquium Comput. Complex. 27 (2020)
Pranav Bisht, Nitin Saxena
Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs. Electron. Colloquium Comput. Complex. 27 (2020)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications. Computational Complexity Conference (2019)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Efficiently factoring polynomials modulo $p^4$. Electron. Colloquium Comput. Complex. 26 (2019)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications. CoRR (2019)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications. Electron. Colloquium Comput. Complex. 26 (2019)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
. CoRR (2019)
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Efficiently Factoring Polynomials Modulo p4. ISSAC (2019)
Zeyu Guo, Nitin Saxena, Amit Sinhababu
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field. Theory Comput. 15 (2019)
Meena Mahajan, Madhavan Mukund, Nitin Saxena
Research in theoretical computer science. Commun. ACM 62 (11) (2019)
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Discovering the roots: uniform closure results for algebraic classes under factoring. STOC (2018)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. Algorithmica 80 (2) (2018)
Anurag Pandey, Nitin Saxena, Amit Sinhababu
Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Comput. Complex. 27 (4) (2018)
Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Towards blackbox identity testing of log-variate circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Zeyu Guo, Nitin Saxena, Amit Sinhababu
Algebraic dependencies and PSPACE algorithms in approximative complexity. Electron. Colloquium Comput. Complex. 25 (2018)
Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Towards Blackbox Identity Testing of Log-Variate Circuits. ICALP (2018)
Zeyu Guo, Nitin Saxena, Amit Sinhababu
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. Computational Complexity Conference (2018)
Zeyu Guo, Nitin Saxena, Amit Sinhababu
Algebraic dependencies and PSPACE algorithms in approximative complexity. CoRR (2018)
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena
Bootstrapping variables in algebraic circuits. STOC (2018)
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena
Bootstrapping variables in algebraic circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena
Irreducibility and deterministic r-th root finding over finite fields. Electron. Colloquium Comput. Complex. 24 (2017)
Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. Electron. Colloquium Comput. Complex. 24 (2017)
Rohit Gurjar, Arpita Korwar, Nitin Saxena
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs. Theory Comput. 13 (1) (2017)
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Discovering the roots: Uniform closure results for algebraic classes under factoring. Electron. Colloquium Comput. Complex. 24 (2017)
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena
Irreducibility and Deterministic r-th Root Finding over Finite Fields. ISSAC (2017)
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Discovering the roots: Uniform closure results for algebraic classes under factoring. CoRR (2017)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Comput. Complex. 26 (4) (2017)
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena
Irreducibility and r-th root finding over finite fields. CoRR (2017)
Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. CoRR (2017)
Anurag Pandey, Nitin Saxena, Amit Sinhababu
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits. MFCS (2016)
Rohit Gurjar, Arpita Korwar, Nitin Saxena
Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. Computational Complexity Conference (2016)
Rohit Gurjar, Arpita Korwar, Nitin Saxena
Identity Testing for constant-width, and commutative, read-once oblivious ABPs. Electron. Colloquium Comput. Complex. 23 (2016)
Manindra Agrawal, Nitin Saxena, Shubham Sahai Srivastava
Integer Factoring Using Small Algebraic Dependencies. MFCS (2016)
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits. SIAM J. Comput. 45 (4) (2016)
Rohit Gurjar, Arpita Korwar, Nitin Saxena
Identity Testing for constant-width, and commutative, read-once oblivious ABPs. CoRR (2016)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. CoRR (2015)
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44 (3) (2015)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. Computational Complexity Conference (2015)
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Hitting-sets for ROABP and Sum of Set-Multilinear circuits. CoRR (2014)
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Hitting-sets for ROABP and Sum of Set-Multilinear circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read Once ABPs. Electron. Colloquium Comput. Complex. 21 (2014)
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic polynomial factoring and association schemes. LMS J. Comput. Math. 17 (1) (2014)
Nitin Saxena
Progress on Polynomial Identity Testing - II. CoRR (2014)
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Deterministic Identity Testing for Sum of Read Once ABPs. CoRR (2014)
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Hitting-sets for low-distance multilinear depth-3. CoRR (2013)
Malte Beecken, Johannes Mittmann, Nitin Saxena
Algebraic independence and blackbox identity testing. Inf. Comput. 222 (2013)
Manindra Agrawal, Chandan Saha, Nitin Saxena
Quasi-polynomial hitting-set for set-depth-Δ formulas. STOC (2013)
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena
Hitting-sets for low-distance multilinear depth-3. Electron. Colloquium Comput. Complex. 20 (2013)
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality. Comput. Complex. 22 (1) (2013)
Nitin Saxena
Progress on Polynomial Identity Testing - II. Electron. Colloquium Comput. Complex. 20 (2013)
Nitin Saxena, C. Seshadhri
From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM 60 (5) (2013)
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Factoring and Association Schemes CoRR (2012)
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Math. Comput. 81 (277) (2012)
Manindra Agrawal, Chandan Saha, Nitin Saxena
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas. Electron. Colloquium Comput. Complex. 19 (2012)
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Factoring and Association Schemes. Electron. Colloquium Comput. Complex. 19 (2012)
Nitin Saxena, C. Seshadhri
Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter. SIAM J. Comput. 41 (5) (2012)
Manindra Agrawal, Chandan Saha, Nitin Saxena
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas CoRR (2012)
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. STOC (2012)
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner
Algebraic Independence in Positive Characteristic -- A p-Adic Calculus CoRR (2012)
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. Electron. Colloquium Comput. Complex. 19 (2012)
Malte Beecken, Johannes Mittmann, Nitin Saxena
Algebraic Independence and Blackbox Identity Testing. ICALP (2) (2011)
Malte Beecken, Johannes Mittmann, Nitin Saxena
Algebraic Independence and Blackbox Identity Testing CoRR (2011)
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. Electron. Colloquium Comput. Complex. 18 (2011)
Nitin Saxena, C. Seshadhri
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. STOC (2011)
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality. Electron. Colloquium Comput. Complex. 18 (2011)
Malte Beecken, Johannes Mittmann, Nitin Saxena
Algebraic Independence and Blackbox Identity Testing. Electron. Colloquium Comput. Complex. 18 (2011)
Nitin Saxena, C. Seshadhri
An Almost Optimal Rank Bound for Depth-3 Identities. SIAM J. Comput. 40 (1) (2011)
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits CoRR (2011)
Nitin Saxena, C. Seshadhri
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits. Electron. Colloquium Comput. Complex. 17 (2010)
Nitin Saxena, C. Seshadhri
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter CoRR (2010)
Nitin Saxena, C. Seshadhri
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits. FOCS (2010)
Nitin Saxena, C. Seshadhri
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. Electron. Colloquium Comput. Complex. 17 (2010)
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. 39 (8) (2010)
Nitin Saxena, C. Seshadhri
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits CoRR (2010)
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
The Power of Depth 2 Circuits over Algebras CoRR (2009)

Nitin Saxena.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Nitin Saxena