Nitin Saxena

Orcid: 0000-0001-6931-898X

Affiliations:
  • ITT Kanpur, India


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply VP ≠q VNP.
Comput. Complex., June, 2024

How Easy Is It to Describe Hard Polynomials?: Technical Perspective.
Commun. ACM, February, 2024

Solving polynomial systems over non-fields and applications to modular polynomial factoring.
J. Symb. Comput., 2024

Lower Bounds for the Sum of Small-Size Algebraic Branching Programs.
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.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023
VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme.
IACR Cryptol. ePrint Arch., 2023

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

An effective description of the roots of bivariates mod pk and the related Igusa's local zeta function.
Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

2022
Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits.
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials.
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.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Efficiently factoring polynomials modulo <i>p</i><sup>4</sup>.
J. Symb. Comput., 2021

Blackbox identity testing for sum of special ROABPs and its border class.
Comput. Complex., 2021

A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Demystifying the border of depth-3 algebraic circuits.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits.
Proceedings of the 36th Computational Complexity Conference, 2021

2020
Computing Igusa's local zeta function of univariates in deterministic polynomial-time.
Electron. Colloquium Comput. Complex., 2020

Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT.
Electron. Colloquium Comput. Complex., 2020

Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs.
Electron. Colloquium Comput. Complex., 2020

Special-case algorithms for blackbox radical membership, nullstellensatz and transcendence degree.
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.
Theory Comput., 2019

Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications.
Electron. Colloquium Comput. Complex., 2019

Efficiently factoring polynomials modulo $p^4$.
Electron. Colloquium Comput. Complex., 2019

Efficiently factoring polynomials modulo p<sup>4</sup>.
CoRR, 2019

Research in theoretical computer science.
Commun. ACM, 2019

Efficiently Factoring Polynomials Modulo p4.
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019

2018
Algebraic dependencies and PSPACE algorithms in approximative complexity.
Electron. Colloquium Comput. Complex., 2018

Towards blackbox identity testing of log-variate circuits.
Electron. Colloquium Comput. Complex., 2018

Bootstrapping variables in algebraic circuits.
Electron. Colloquium Comput. Complex., 2018

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

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

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

Discovering the roots: Uniform closure results for algebraic classes under factoring.
Electron. Colloquium Comput. Complex., 2017

Irreducibility and deterministic r-th root finding over finite fields.
Electron. Colloquium Comput. Complex., 2017

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.
Electron. Colloquium Comput. Complex., 2017

Irreducibility and r-th root finding over finite fields.
CoRR, 2017

Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs.
Comput. Complex., 2017

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

Identity Testing for constant-width, and commutative, read-once oblivious ABPs.
Electron. Colloquium Comput. Complex., 2016

Integer Factoring Using Small Algebraic Dependencies.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits.
SIAM J. Comput., 2015

2014
Deterministic polynomial factoring and association schemes.
LMS J. Comput. Math., 2014

Deterministic Identity Testing for Sum of Read Once ABPs.
Electron. Colloquium Comput. Complex., 2014

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

Progress on Polynomial Identity Testing - II.
Electron. Colloquium Comput. Complex., 2013

Hitting-sets for low-distance multilinear depth-3.
Electron. Colloquium Comput. Complex., 2013

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

Quasi-polynomial hitting-set for set-depth-Δ formulas.
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.
SIAM J. Comput., 2012

Trading GRH for algebra: Algorithms for factoring polynomials and related structures.
Math. Comput., 2012

Algebraic Independence in Positive Characteristic - A p-Adic Calculus.
Electron. Colloquium Comput. Complex., 2012

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas.
Electron. Colloquium Comput. Complex., 2012

2011
An Almost Optimal Rank Bound for Depth-3 Identities.
SIAM J. Comput., 2011

Algebraic Independence and Blackbox Identity Testing.
Electron. Colloquium Comput. Complex., 2011

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

2010
Deterministic Polynomial Time Algorithms for Matrix Completion Problems.
SIAM J. Comput., 2010

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.
Electron. Colloquium Comput. Complex., 2010

2009
Progress on Polynomial Identity Testing.
Electron. Colloquium Comput. Complex., 2009

The Power of Depth 2 Circuits over Algebras.
Electron. Colloquium Comput. Complex., 2009

2008
Schemes for Deterministic Polynomial Factoring.
Electron. Colloquium Comput. Complex., 2008

2007
Diagonal Circuit Identity Testing and Lower Bounds.
Electron. Colloquium Comput. Complex., 2007

Polynomial Identity Testing for Depth 3 Circuits.
Comput. Complex., 2007

2006
Complexity of Ring Morphism Problems.
Comput. Complex., 2006

Equivalence of F-Algebras and Cubic Forms.
Proceedings of the STACS 2006, 2006

2005
Automorphisms of Finite Rings and Applications to Complexity of Problems.
Proceedings of the STACS 2005, 2005

On the Ring Isomorphism and Automorphism Problems.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
On the Ring Isomorphism & Automorphism Problems
Electron. Colloquium Comput. Complex., 2004


  Loading...