Nitin Saxena

Madhavan Venkatesh

CoRR, November, 2025

A primer on the closure of algebraic complexity classes under factoring.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals.

[BibT_eX]

[DOI]

Abhibhav Garg

Rafael Oliveira

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

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

[BibT_eX]

[DOI]

Thomas Thierauf

Comput. Complex., June, 2024

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

[BibT_eX]

[DOI]

Commun. ACM, February, 2024

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

[BibT_eX]

[DOI]

Sayak Chakrabarti

J. Symb. Comput., 2024

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2023

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

[BibT_eX]

[DOI]

Rishabh Batra

Devansh Shringi

Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Sayak Chakrabarti

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

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

[BibT_eX]

[DOI]

Anindya Ganguly

Angshuman Karmakar

Proceedings of the Progress in Cryptology - INDOCRYPT 2023, 2023

2022

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

[BibT_eX]

[DOI]

Sagnik Dutta

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

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

[BibT_eX]

[DOI]

Pranav Bisht

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.

[BibT_eX]

[DOI]

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

2021

Efficiently factoring polynomials modulo p4.

[BibT_eX]

[DOI]

J. Symb. Comput., 2021

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

[BibT_eX]

[DOI]

Pranav Bisht

Comput. Complex., 2021

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

[BibT_eX]

[DOI]

Thomas Thierauf

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

Demystifying the border of depth-3 algebraic circuits.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Thomas Thierauf

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Pranav Bisht

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Abhibhav Garg

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.

[BibT_eX]

[DOI]

Zeyu Guo

Theory Comput., 2019

Efficiently factoring polynomials modulo $p^4$.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Efficiently factoring polynomials modulo p4.

[BibT_eX]

[DOI]

CoRR, 2019

Research in theoretical computer science.

[BibT_eX]

[DOI]

Meena Mahajan

Madhavan Mukund

Commun. ACM, 2019

Efficiently Factoring Polynomials Modulo p4.

[BibT_eX]

[DOI]

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

Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

Algorithmica, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Bootstrapping variables in algebraic circuits.

[BibT_eX]

[DOI]

Sumanta Ghosh

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards Blackbox Identity Testing of Log-Variate Circuits.

[BibT_eX]

[DOI]

Michael A. Forbes

Sumanta Ghosh

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity.

[BibT_eX]

[DOI]

Zeyu Guo

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

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

[BibT_eX]

[DOI]

Rohit Gurjar

Arpita Korwar

Theory Comput., 2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Irreducibility and r-th root finding over finite fields.

[BibT_eX]

[DOI]

CoRR, 2017

Irreducibility and Deterministic r-th Root Finding over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017

2016

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits.

[BibT_eX]

[DOI]

Anurag Pandey

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

Integer Factoring Using Small Algebraic Dependencies.

[BibT_eX]

[DOI]

Shubham Sahai Srivastava

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

Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs.

[BibT_eX]

[DOI]

Rohit Gurjar

Arpita Korwar

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

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

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Deterministic Identity Testing for Sum of Read Once ABPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Hitting-sets for ROABP and Sum of Set-Multilinear circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

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

[BibT_eX]

[DOI]

J. ACM, 2013

Progress on Polynomial Identity Testing - II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

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

[BibT_eX]

[DOI]

Johannes Mittmann

Peter Scheiblechner

Electron. Colloquium Comput. Complex., 2012

Deterministic Polynomial Factoring and Association Schemes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Algebraic Independence and Blackbox Identity Testing.

[BibT_eX]

[DOI]

Malte Beecken

Johannes Mittmann

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

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

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Progress on Polynomial Identity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Deterministic Polynomial Time Algorithms for Matrix Completion Problems.

[BibT_eX]

[DOI]

Gábor Ivanyos

Marek Karpinski

Electron. Colloquium Comput. Complex., 2009

Schemes for deterministic polynomial factoring.

[BibT_eX]

[DOI]

Gábor Ivanyos

Marek Karpinski

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2009

The Power of Depth 2 Circuits over Algebras.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

An Almost Optimal Rank Bound for Depth-3 Identities.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

2007

Diagonal Circuit Identity Testing and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006

Complexity of Ring Morphism Problems.

[BibT_eX]

[DOI]

Comput. Complex., 2006

Equivalence of F-Algebras and Cubic Forms.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

Polynomial Identity Testing for Depth 3 Circuits.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Automorphisms of Finite Rings and Applications to Complexity of Problems.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

On the Ring Isomorphism and Automorphism Problems.

[BibT_eX]

[DOI]

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

2004

On the Ring Isomorphism & Automorphism Problems

[BibT_eX]

[DOI]