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

Testing Equivalence to Design Polynomials.

Omkar Baraskar, Agrim Dewan, Chandan Saha

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials.

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Equivalence Test for Read-Once Arithmetic Formulas.

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 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

Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case.

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Proceedings of the Approximation, 2022

2021

Hitting Sets for Orbits of Circuit Classes and Polynomial Families.

Chandan Saha, Bhargav Thankey

Proceedings of the Approximation, 2021

2020

Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests.

Janaky Murthy, Vineet Nair, Chandan Saha

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

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

Ankit Garg, Neeraj Kayal, Chandan Saha

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Proceedings of the 35th Computational Complexity Conference, 2020

2019

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

Neeraj Kayal, Vineet Nair, Chandan Saha

Comput. Complex., 2019

Reconstruction of non-degenerate homogeneous depth three circuits.

Neeraj Kayal, Chandan Saha

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 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

Determinant Equivalence Test over Finite Fields and over Q.

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.

Neeraj Kayal, Chandan Saha

SIGACT News, 2018

On the symmetries of design polynomials.

Nikhil Gupta, Chandan Saha

Electron. Colloquium Comput. Complex., 2018

2017

Reconstruction of Full Rank Algebraic Branching Programs.

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

Proceedings of the 32nd Computational Complexity Conference, 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

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

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

Neeraj Kayal, Vineet Nair, Chandan Saha

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits.

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

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

Multi-k-ic Depth Three Circuit Lower Bound.

Neeraj Kayal, Chandan Saha

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 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

Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin.

Neeraj Kayal, Chandan Saha

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Proceedings of the Symposium on Theory of Computing, 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

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

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

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

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

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

On the Sum of Square Roots of Polynomials and Related Problems.

Neeraj Kayal, Chandan Saha

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2009

The Power of Depth 2 Circuits over Algebras.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

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

2008

Fast integer multiplication using modular arithmetic.

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

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Factoring Polynomials over Finite Fields using Balance Test.

Chandan Saha

Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008

2007

Covering a Set of Points in a Plane Using Two Parallel Rectangles.

Chandan Saha, Sandip Das

Proceedings of the 2007 International Conference on Computing: Theory and Applications (ICCTA 2007), 2007

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