Chandan Saha

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials	2024	Omkar Baraskar Agrim Dewan Chandan Saha Pranay Sinha
+	Low-depth arithmetic circuit lower bounds via shifted partials	2022	Prashanth Amireddy Ankit Garg Neeraj Kayal Chandan Saha Bhargav Thankey
+ PDF Chat	Learning sums of powers of low-degree polynomials in the non-degenerate case	2020	Ankit Garg Neeraj Kayal Chandan Saha
+	A super-quadratic lower bound for depth four arithmetic circuits	2020	Nïkhil Gupta Chandan Saha Bhargav Thankey
+	Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests	2020	Janaky Murthy Vineet Nair Chandan Saha
+	Learning sums of powers of low-degree polynomials in the non-degenerate case	2020	Ankit Garg Neeraj Kayal Chandan Saha
+ PDF Chat	Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits	2020	Neeraj Kayal Vineet Nair Chandan Saha
+	Learning sums of powers of low-degree polynomials in the non-degenerate case.	2020	Ankit Garg Neeraj Kayal Chandan Saha
+	A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits.	2020	Nïkhil Gupta Chandan Saha Bhargav Thankey
+	Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests	2020	Janaky Murthy Vineet Nair Chandan Saha
+	Learning sums of powers of low-degree polynomials in the non-degenerate case	2020	Ankit Garg Neeraj Kayal Chandan Saha
+ PDF Chat	On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree	2018	Neeraj Kayal Chandan Saha Sébastien Tavenas
+	Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits	2016	Neeraj Kayal Vineet Nair Chandan Saha
+	Lower Bounds for Sums of Powers of Low Degree Univariates	2015	Neeraj Kayal Pascal Koiran Timothée Pecatte Chandan Saha
+	Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits.	2015	Neeraj Kayal Vineet Nair Chandan Saha
+	An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas	2014	Neeraj Kayal Nutan Limaye Chandan Saha Srikanth Srinivasan
+	A super-polynomial lower bound for regular arithmetic formulas	2014	Neeraj Kayal Chandan Saha Ramprasad Saptharishi
+	An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.	2014	Neeraj Kayal Nutan Limaye Chandan Saha Srikanth Srinivasan
+ PDF Chat	Fast Integer Multiplication Using Modular Arithmetic	2013	Anindya De Piyush P. Kurur Chandan Saha Ramprasad Saptharishi
+	A super-polynomial lower bound for regular arithmetic formulas.	2013	Neeraj Kayal Chandan Saha Ramprasad Saptharishi
+	Quasi-polynomial Hitting-set for Set-depth-Delta Formulas	2012	Manindra Agrawal Chandan Saha Nitin Saxena
+	Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits	2011	Manindra Agrawal Chandan Saha Ramprasad Saptharishi Nitin Saxena
+	Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant	2011	Michael A. Forbes Neeraj Kayal Rajat Mittal Chandan Saha
+	Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant	2011	Michael Forbes Neeraj Kayal Rajat Mittal Chandan Saha
+	The Power of Depth 2 Circuits over Algebras	2009	Chandan Saha Ramprasad Saptharishi Nitin Saxena
+	Factoring Polynomials over Finite Fields using Balance Test	2008	Chandan Saha
+	Fast Integer Multiplication using Modular Arithmetic.	2008	Anindya De Piyush P. Kurur Chandan Saha Ramprasad Saptharishi
+	Fast Integer Multiplication using Modular Arithmetic	2008	Anindya De Piyush P. Kurur Chandan Saha Ramprasad Saptharishi

Common Coauthors

Coauthor	Papers Together
Neeraj Kayal	16
Ramprasad Saptharishi	7
Vineet Nair	5
Nitin Saxena	3
Piyush P. Kurur	3
Bhargav Thankey	3
Anindya De	3
Ankit Garg	3
Srikanth Srinivasan	2
Rajat Mittal	2
Manindra Agrawal	2
Ankit Garg	2
Nïkhil Gupta	2
Janaky Murthy	2
Nutan Limaye	2
Agrim Dewan	1
Timothée Pecatte	1
Pranay Sinha	1
Prashanth Amireddy	1
Pascal Koiran	1
Michael Forbes	1
Sébastien Tavenas	1
Omkar Baraskar	1
Michael A. Forbes	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	Completeness classes in algebra	1979	Leslie G. Valiant	7
+	Arithmetic circuits: The chasm at depth four gets wider	2012	Pascal Koiran	6
+	Multi-linear formulas for permanent and determinant are of super-polynomial size	2009	Ran Raz	6
+ PDF Chat	Improved Bounds for Reduction to Depth 4 and Depth 3	2013	Sébastien Tavenas	5
+	A super-polynomial lower bound for regular arithmetic formulas	2014	Neeraj Kayal Chandan Saha Ramprasad Saptharishi	5
+	Partial Derivatives in Arithmetic Complexity and Beyond	2010	Xi Chen Neeraj Kayal Avi Wigderson	4
+ PDF Chat	Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression	1992	D. R. Heath‐Brown	3
+ PDF Chat	On the Power of Homogeneous Depth 4 Arithmetic Circuits	2017	Mrinal Kumar Shubhangi Saraf	3
+	An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas	2014	Neeraj Kayal Nutan Limaye Chandan Saha Srikanth Srinivasan	3
+	Probabilistic algorithms for sparse polynomials	1979	Richard Zippel	3
+	Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits	2016	Neeraj Kayal Vineet Nair Chandan Saha	3
+	A divisor problem	1930	E. C. Titchmarsh	3
+ PDF Chat	Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas	2016	Rafael Oliveira Amir Shpilka Ben Lee Volk	3
+	Tensor rank is NP-complete	1990	Johan Håstad	2
+ PDF Chat	Tensor-rank and lower bounds for arithmetic formulas	2010	Ran Raz	2
+	Decompositions of algebras over ? and ?	1991	Wayne Eberly	2
+	A Decomposition for Three-Way Arrays	1993	Sue E. Leurgans R. Ross Robert Abel	2
+	An Introduction to the Theory of Numbers.	1961	W. J. LeVeque Ivan Niven Herbert S. Zuckerman	2
+	Algebraic Independence and Blackbox Identity Testing	2011	Malte Beecken Johannes Mittmann Nitin Saxena	2
+	Basic notions of algebra	2005	Igor R. Shafarevich	2
+ PDF Chat	On the Power of Homogeneous Depth 4 Arithmetic Circuits	2014	Mrinal Kumar Shubhangi Saraf	2
+ PDF Chat	Smoothed analysis of tensor decompositions	2014	Aditya Bhaskara Moses Charikar Ankur Moitra Aravindan Vijayaraghavan	2
+ PDF Chat	Character theory of finite groups	1999	I. M. Isaacs	2
+	Faster integer multiplication	2007	Martin Fürer	2
+	Primes representable by polynomials and the lower bound of the least primes in arithmetic progressions	1990	Tianxin Cai	2
+	Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-model factor analysis	1970	Richard A. Harshman	2
+	Computing the structure of finite algebras	1990	Lajos Rónyai	2
+ PDF Chat	Factoring polynomials with rational coefficients	1982	A. K. Lenstra H. W. Lenstra László Lovász	2
+	Polynomial Equivalence Problems for Sum of Affine Powers	2018	Ignacio García-Marco Pascal Koiran Timothée Pecatte	2
+	Efficient algorithms for some special cases of the polynomial equivalence problem	2011	Neeraj Kayal	2
+ PDF Chat	Learning Mixtures of Gaussians in High Dimensions	2015	Rong Ge Qingqing Huang Sham M. Kakade	2
+ PDF Chat	Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties	2008	Ketan Mulmuley Milind Sohoni	1
+	Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms	2015	Rong Ge Tengyu Ma	1
+	On Spectral Learning of Mixtures of Distributions	2005	Dimitris Achlioptas Frank McSherry	1
+	λ1, Isoperimetric inequalities for graphs, and superconcentrators	1985	Noga Alon Vitali Milman	1
+	On Representatives of Subsets	1935	P. Hall	1
+ PDF Chat	Tensor-Rank and Lower Bounds for Arithmetic Formulas	2013	Ran Raz	1
+ PDF Chat	Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits	2015	Manindra Agrawal Rohit Gurjar Arpita Korwar Nitin Saxena	1
+	Elements of number theory	1954	Ivan Matveevich Vinogradov Saul Kravetz	1
+	Multiplicative Number Theory	1980	H. Davenport	1
+ PDF Chat	Lower Bounds for Tropical Circuits and Dynamic Programs	2014	Stasys Jukna	1
+	Affine projections of polynomials	2012	Neeraj Kayal	1
+ PDF Chat	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method	2015	Boaz Barak Jonathan A. Kelner David Steurer	1
+	Wronskian determinants and the zeros of certain functions	1975	Marc Voorhoeve van der Poorten	1
+ PDF Chat	Homogeneous Formulas and Symmetric Polynomials	2011	Pavel Hrubeš Amir Yehudayoff	1
+ PDF Chat	Learning nonsingular phylogenies and hidden Markov models	2005	Elchanan Mossel Sébastien Roch	1
+ PDF Chat	Deterministic Polynomial Time Algorithms for Matrix Completion Problems	2010	Gábor Ivanyos Marek Karpiński Nitin Saxena	1
+ PDF Chat	Clustering with Spectral Norm and the k-Means Algorithm	2010	Amit Kumar Ravindran Kannan	1
+	Zero-free regions for Dirichlet L-functions	1999	H. Li	1
+ PDF Chat	Settling the Polynomial Learnability of Mixtures of Gaussians	2010	Ankur Moitra Gregory Valiant	1