Chandan Saha

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 50

Top Topics

Matrix Factorization

Scaled Orthographic

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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