Chandan Saha

85 papers A* 15A 9B 2Journal 54Unranked 5
YearRankTypeTitle / Venue / Authors
2026 J jnl
Learning Read-Once Determinants and the Principal Minor Assignment Problem.
CoRR
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha
2026 J jnl
Learning Read-Once Determinants and the Principal Minor Assignment Problem.
Electron. Colloquium Comput. Complex.
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha
2024 J jnl
Hitting Sets for Orbits of Circuit Classes and Polynomial Families.
ACM Trans. Comput. Theory
Chandan Saha, Bhargav Thankey
2024 A* conf
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials.
ICALP
Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha
2024 J jnl
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials.
CoRR
Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha
2024 J jnl
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials.
Electron. Colloquium Comput. Complex.
Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha
2024 A conf
Testing Equivalence to Design Polynomials.
STACS
Omkar Baraskar, Agrim Dewan, Chandan Saha
2024 J jnl
Testing equivalence to design polynomials.
Electron. Colloquium Comput. Complex.
Omkar Baraskar, Agrim Dewan, Chandan Saha
2023 A* conf
Equivalence Test for Read-Once Arithmetic Formulas.
SODA
Nikhil Gupta, Chandan Saha, Bhargav Thankey
2023 A* conf
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization.
ICALP
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
2022 J jnl
Equivalence Test for Read-Once Arithmetic Formulas.
Electron. Colloquium Comput. Complex.
Nikhil Gupta, Chandan Saha, Bhargav Thankey
2022 A conf
Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case.
APPROX/RANDOM
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha
2022 J jnl
Low-depth arithmetic circuit lower bounds via shifted partials.
CoRR
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
2022 J jnl
Low-depth arithmetic circuit lower bounds via shifted partials.
Electron. Colloquium Comput. Complex.
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
2021 — conf
Hitting Sets for Orbits of Circuit Classes and Polynomial Families.
APPROX-RANDOM
Chandan Saha, Bhargav Thankey
2021 J jnl
Hitting Sets for Orbits of Circuit Classes and Polynomial Families.
Electron. Colloquium Comput. Complex.
Chandan Saha, Bhargav Thankey
2021 J jnl
Learning generalized depth-three arithmetic circuits in the non-degenerate case.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha
2020 A conf
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits.
CCC
Nikhil Gupta, Chandan Saha, Bhargav Thankey
2020 J jnl
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Nikhil Gupta, Chandan Saha, Bhargav Thankey
2020 A* conf
Learning sums of powers of low-degree polynomials in the non-degenerate case.
FOCS
Ankit Garg, Neeraj Kayal, Chandan Saha
2020 J jnl
Learning sums of powers of low-degree polynomials in the non-degenerate case.
CoRR
Ankit Garg, Neeraj Kayal, Chandan Saha
2020 J jnl
Learning sums of powers of low-degree polynomials in the non-degenerate case.
Electron. Colloquium Comput. Complex.
Ankit Garg, Neeraj Kayal, Chandan Saha
2020 B conf
Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests.
MFCS
Janaky Murthy, Vineet Nair, Chandan Saha
2020 J jnl
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests.
CoRR
Janaky Murthy, Vineet Nair, Chandan Saha
2020 J jnl
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests.
Electron. Colloquium Comput. Complex.
Janaky Murthy, Vineet Nair, Chandan Saha
2020 J jnl
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits.
ACM Trans. Comput. Theory
Neeraj Kayal, Vineet Nair, Chandan Saha
2019 J jnl
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs.
Comput. Complex.
Neeraj Kayal, Vineet Nair, Chandan Saha
2019 A* conf
Determinant Equivalence Test over Finite Fields and over Q.
ICALP
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha
2019 J jnl
Determinant equivalence test over finite fields and over ℚ.
Electron. Colloquium Comput. Complex.
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha
2019 B conf
On the Symmetries of and Equivalence Test for Design Polynomials.
MFCS
Nikhil Gupta, Chandan Saha
2019 J jnl
Reconstruction of Full Rank Algebraic Branching Programs.
ACM Trans. Comput. Theory
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
2019 A* conf
Reconstruction of non-degenerate homogeneous depth three circuits.
STOC
Neeraj Kayal, Chandan Saha
2018 J jnl
Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Vineet Nair, Chandan Saha
2018 J jnl
Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.
SIGACT News
Neeraj Kayal, Chandan Saha
2018 J jnl
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree.
Theory Comput.
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
2018 J jnl
On the symmetries of design polynomials.
Electron. Colloquium Comput. Complex.
Nikhil Gupta, Chandan Saha
2018 J jnl
Reconstruction of non-degenerate homogeneous depth three circuits.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha
2017 J jnl
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.
SIAM J. Comput.
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
2017 J jnl
Multi-k-ic Depth Three Circuit Lower Bound.
Theory Comput. Syst.
Neeraj Kayal, Chandan Saha
2017 A conf
Reconstruction of Full Rank Algebraic Branching Programs.
CCC
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
2017 J jnl
Reconstruction of full rank Algebraic Branching Programs.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas
2016 A* conf
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits.
ICALP
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
2016 J jnl
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
2016 J jnl
Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits.
SIAM J. Comput.
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2016 J jnl
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin.
Comput. Complex.
Neeraj Kayal, Chandan Saha
2016 A* conf
On the size of homogeneous and of depth four formulas with low individual degree.
STOC
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
2016 A conf
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.
STACS
Neeraj Kayal, Vineet Nair, Chandan Saha
2015 A conf
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin.
CCC
Neeraj Kayal, Chandan Saha
2015 — conf
Lower Bounds for Sums of Powers of Low Degree Univariates.
ICALP (1)
Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha
2015 J jnl
Lower Bounds for Sums of Products of Low arity Polynomials.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha
2015 J jnl
Multi-
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha
2015 A conf
Multi-k-ic Depth Three Circuit Lower Bound.
STACS
Neeraj Kayal, Chandan Saha
2015 J jnl
On the size of homogeneous and of depth four formulas with low individual degree.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha, Sébastien Tavenas
2015 J jnl
Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Vineet Nair, Chandan Saha
2014 A* conf
A super-polynomial lower bound for regular arithmetic formulas.
STOC
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
2014 A* conf
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.
FOCS
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
2014 J jnl
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
2014 J jnl
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha
2014 A* conf
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.
STOC
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
2013 J jnl
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.
Comput. Complex.
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2013 J jnl
A super-polynomial lower bound for regular arithmetic formulas.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
2013 J jnl
Fast Integer Multiplication Using Modular Arithmetic.
SIAM J. Comput.
Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi
2013 A* conf
Quasi-polynomial hitting-set for set-depth-Δ formulas.
STOC
Manindra Agrawal, Chandan Saha, Nitin Saxena
2012 A* conf
Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.
STOC
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2012 J jnl
On the Sum of Square Roots of Polynomials and Related Problems.
ACM Trans. Comput. Theory
Neeraj Kayal, Chandan Saha
2012 J jnl
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas.
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Chandan Saha, Nitin Saxena
2012 J jnl
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas
CoRR
Manindra Agrawal, Chandan Saha, Nitin Saxena
2011 J jnl
A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.
Electron. Colloquium Comput. Complex.
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2011 J jnl
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
CoRR
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2011 J jnl
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2011 A conf
On the Sum of Square Roots of Polynomials and Related Problems.
CCC
Neeraj Kayal, Chandan Saha
2011 J jnl
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
CoRR
Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha
2010 J jnl
On the Sum of Square Roots of Polynomials and related problems.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Chandan Saha
2009 J jnl
Covering a set of points in a plane using two parallel rectangles.
Inf. Process. Lett.
Chandan Saha, Sandip Das
2009 J jnl
The Power of Depth 2 Circuits over Algebras
CoRR
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2009 — conf
The Power of Depth 2 Circuits over Algebras.
FSTTCS
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2009 J jnl
The Power of Depth 2 Circuits over Algebras.
Electron. Colloquium Comput. Complex.
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
2008 J jnl
Factoring Polynomials over Finite Fields using Balance Test
CoRR
Chandan Saha
2008 A conf
Factoring Polynomials over Finite Fields using Balance Test.
STACS
Chandan Saha
2008 J jnl
Fast Integer Multiplication using Modular Arithmetic
CoRR
Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi
2008 J jnl
Fast Integer Multiplication using Modular Arithmetic.
Electron. Colloquium Comput. Complex.
Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi
2008 A* conf
Fast integer multiplication using modular arithmetic.
STOC
Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi
2007 — conf
Covering a Set of Points in a Plane Using Two Parallel Rectangles.
ICCTA
Chandan Saha, Sandip Das
2006 A* conf
Simpler algorithm for estimating frequency moments of data streams.
SODA
Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, Chandan Saha
2005 — conf
Practical Algorithms for Tracking Database Join Sizes.
FSTTCS
Sumit Ganguly, Deepanjan Kesh, Chandan Saha