Chandan Saha

According to our database, Chandan Saha authored at least 41 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials.

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

Electron. Colloquium Comput. Complex., 2024

Testing equivalence to design polynomials.

Omkar Baraskar, Agrim Dewan, Chandan Saha

Electron. Colloquium Comput. Complex., 2024

2023

Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Low-depth arithmetic circuit lower bounds via shifted partials.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2022

Equivalence Test for Read-Once Arithmetic Formulas.

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2022

2021

Hitting Sets for Orbits of Circuit Classes and Polynomial Families.

Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2021

Learning generalized depth-three arithmetic circuits in the non-degenerate case.

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2021

2020

Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests.

Janaky Murthy, Vineet Nair, Chandan Saha

Electron. Colloquium Comput. Complex., 2020

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits.

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2020

Learning sums of powers of low-degree polynomials in the non-degenerate case.

Ankit Garg, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2020

2019

Determinant equivalence test over finite fields and over ℚ.

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2019

Average-case linear matrix factorization and reconstruction of low width algebraic branching programs.

Neeraj Kayal, Vineet Nair, Chandan Saha

Comput. Complex., 2019

On the Symmetries of and Equivalence Test for Design Polynomials.

Nikhil Gupta, Chandan Saha

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.

Neeraj Kayal, Chandan Saha

SIGACT News, 2018

Reconstruction of non-degenerate homogeneous depth three circuits.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2018

On the symmetries of design polynomials.

Nikhil Gupta, Chandan Saha

Electron. Colloquium Comput. Complex., 2018

2017

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

SIAM J. Comput., 2017

Multi-k-ic Depth Three Circuit Lower Bound.

Neeraj Kayal, Chandan Saha

Theory Comput. Syst., 2017

Reconstruction of full rank Algebraic Branching Programs.

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2017

2016

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

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

SIAM J. Comput., 2016

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin.

Neeraj Kayal, Chandan Saha

Comput. Complex., 2016

2015

On the size of homogeneous and of depth four formulas with low individual degree.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2015

Lower Bounds for Sums of Products of Low arity Polynomials.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2015

Multi-<i>k</i>-ic depth three circuit lower bound.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2015

Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.

Neeraj Kayal, Vineet Nair, Chandan Saha

Electron. Colloquium Comput. Complex., 2015

Lower Bounds for Sums of Powers of Low Degree Univariates.

Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the Symposium on Theory of Computing, 2014

2013

Fast Integer Multiplication Using Modular Arithmetic.

Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi

SIAM J. Comput., 2013

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2013

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

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Comput. Complex., 2013

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

Manindra Agrawal, Chandan Saha, Nitin Saxena

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

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

Manindra Agrawal, Chandan Saha, Nitin Saxena

Electron. Colloquium Comput. Complex., 2012

2011

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

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2011

Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant

Michael Forbes, Neeraj Kayal, Rajat Mittal, Chandan Saha

CoRR, 2011

2010

On the Sum of Square Roots of Polynomials and related problems.

Neeraj Kayal, Chandan Saha

Electron. Colloquium Comput. Complex., 2010

2009

Covering a set of points in a plane using two parallel rectangles.

Chandan Saha, Sandip Das

Inf. Process. Lett., 2009

The Power of Depth 2 Circuits over Algebras.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2009

2008

Factoring Polynomials over Finite Fields using Balance Test.

Chandan Saha

Proceedings of the STACS 2008, 2008

2006

Simpler algorithm for estimating frequency moments of data streams.

Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, Chandan Saha

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Practical Algorithms for Tracking Database Join Sizes.

Sumit Ganguly, Deepanjan Kesh, Chandan Saha

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005