Follow
Chandan Saha
Chandan Saha
Indian Institute of Science
Verified email at iisc.ac.in - Homepage
Title
Cited by
Cited by
Year
Fast integer multiplication using modular arithmetic
A De, PP Kurur, C Saha, R Saptharishi
Proceedings of the fortieth annual ACM symposium on Theory of computing, 499-506, 2008
1232008
Simpler algorithm for estimating frequency moments of data streams
L Bhuvanagiri, S Ganguly, D Kesh, C Saha
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete …, 2006
1152006
An exponential lower bound for homogeneous depth four arithmetic formulas
N Kayal, N Limaye, C Saha, S Srinivasan
SIAM Journal on Computing 46 (1), 307-335, 2017
882017
A super-polynomial lower bound for regular arithmetic formulas
N Kayal, C Saha, R Saptharishi
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
882014
Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth- Occur- Formulas and Depth-3 Transcendence Degree- Circuits
M Agrawal, C Saha, R Saptharishi, N Saxena
SIAM Journal on Computing 45 (4), 1533-1562, 2016
852016
Quasi-polynomial hitting-set for set-depth-Δ formulas
M Agrawal, C Saha, N Saxena
Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013
602013
A case of depth-3 identity testing, sparse factorization and duality
C Saha, R Saptharishi, N Saxena
Computational Complexity 22, 39-69, 2013
372013
An almost cubic lower bound for depth three arithmetic circuits
N Kayal, C Saha, S Tavenas
43rd International Colloquium on Automata, Languages, and Programming (ICALP …, 2016
342016
Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
N Kayal, V Nair, C Saha
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 2016
34*2016
Lower bounds for depth-three arithmetic circuits with small bottom fanin
N Kayal, C Saha
computational complexity 25, 419-454, 2016
332016
On the size of homogeneous and of depth four formulas with low individual degree
N Kayal, C Saha, S Tavenas
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
272016
On the sum of square roots of polynomials and related problems
N Kayal, C Saha
ACM Transactions on Computation Theory (TOCT) 4 (4), 1-15, 2012
262012
Reconstruction of full rank algebraic branching programs
N Kayal, V Nair, C Saha, S Tavenas
ACM Transactions on Computation Theory (TOCT) 11 (1), 1-56, 2018
252018
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
N Kayal, N Limaye, C Saha, S Srinivasan
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
242014
Reconstruction of non-degenerate homogeneous depth three circuits
N Kayal, C Saha
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019
232019
The power of depth 2 circuits over algebras
C Saha, R Saptharishi, N Saxena
arXiv preprint arXiv:0904.2058, 2009
222009
Lower bounds for sums of powers of low degree univariates
N Kayal, P Koiran, T Pecatte, C Saha
Automata, Languages, and Programming: 42nd International Colloquium, ICALP …, 2015
202015
Practical algorithms for tracking database join sizes
S Ganguly, D Kesh, C Saha
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer …, 2005
202005
Learning sums of powers of low-degree polynomials in the non-degenerate case
A Garg, N Kayal, C Saha
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
192020
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
N Kayal, V Nair, C Saha
computational complexity 28, 749-828, 2019
162019
The system can't perform the operation now. Try again later.
Articles 1–20