Chandan Saha

Affiliations:
  • Indian Institute of Science, Department of Computer Science and Automation, India


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials.
Electron. Colloquium Comput. Complex., 2024

Testing equivalence to design polynomials.
Electron. Colloquium Comput. Complex., 2024

2023
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Low-depth arithmetic circuit lower bounds via shifted partials.
Electron. Colloquium Comput. Complex., 2022

Equivalence Test for Read-Once Arithmetic Formulas.
Electron. Colloquium Comput. Complex., 2022

2021
Hitting Sets for Orbits of Circuit Classes and Polynomial Families.
Electron. Colloquium Comput. Complex., 2021

Learning generalized depth-three arithmetic circuits in the non-degenerate case.
Electron. Colloquium Comput. Complex., 2021

2020
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests.
Electron. Colloquium Comput. Complex., 2020

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits.
Electron. Colloquium Comput. Complex., 2020

Learning sums of powers of low-degree polynomials in the non-degenerate case.
Electron. Colloquium Comput. Complex., 2020

2019
Determinant equivalence test over finite fields and over ℚ.
Electron. Colloquium Comput. Complex., 2019

Average-case linear matrix factorization and reconstruction of low width algebraic branching programs.
Comput. Complex., 2019

On the Symmetries of and Equivalence Test for Design Polynomials.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018
Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds.
SIGACT News, 2018

Reconstruction of non-degenerate homogeneous depth three circuits.
Electron. Colloquium Comput. Complex., 2018

On the symmetries of design polynomials.
Electron. Colloquium Comput. Complex., 2018

2017
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.
SIAM J. Comput., 2017

Multi-k-ic Depth Three Circuit Lower Bound.
Theory Comput. Syst., 2017

Reconstruction of full rank Algebraic Branching Programs.
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.
SIAM J. Comput., 2016

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits.
Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin.
Comput. Complex., 2016

2015
On the size of homogeneous and of depth four formulas with low individual degree.
Electron. Colloquium Comput. Complex., 2015

Lower Bounds for Sums of Products of Low arity Polynomials.
Electron. Colloquium Comput. Complex., 2015

Multi-<i>k</i>-ic depth three circuit lower bound.
Electron. Colloquium Comput. Complex., 2015

Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.
Electron. Colloquium Comput. Complex., 2015

Lower Bounds for Sums of Powers of Low Degree Univariates.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.
Proceedings of the Symposium on Theory of Computing, 2014

2013
Fast Integer Multiplication Using Modular Arithmetic.
SIAM J. Comput., 2013

A super-polynomial lower bound for regular arithmetic formulas.
Electron. Colloquium Comput. Complex., 2013

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

Quasi-polynomial hitting-set for set-depth-Δ formulas.
Proceedings of the Symposium on Theory of Computing Conference, 2013

2012
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas.
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.
Electron. Colloquium Comput. Complex., 2011

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

2010
On the Sum of Square Roots of Polynomials and related problems.
Electron. Colloquium Comput. Complex., 2010

2009
Covering a set of points in a plane using two parallel rectangles.
Inf. Process. Lett., 2009

The Power of Depth 2 Circuits over Algebras.
Electron. Colloquium Comput. Complex., 2009

2008
Factoring Polynomials over Finite Fields using Balance Test.
Proceedings of the STACS 2008, 2008

2006
Simpler algorithm for estimating frequency moments of data streams.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Practical Algorithms for Tracking Database Join Sizes.
Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005


  Loading...