# Neeraj Kayal

#4,639

Most Influential Person Now

Indian computer scientist and mathematician

## Neeraj Kayal's AcademicInfluence.com Rankings

Neeraj Kayalmathematics Degrees

Mathematics

#872

World Rank

#1540

Historical Rank

Complexity Theory

#4

World Rank

#4

Historical Rank

Measure Theory

#4670

World Rank

#5468

Historical Rank

## Download Badge

Computer Science Mathematics

## Why Is Neeraj Kayal Influential?

(Suggest an Edit or Addition)According to Wikipedia, Neeraj Kayal is an Indian computer scientist and mathematician noted for development of the AKS primality test, along with Manindra Agrawal and Nitin Saxena. Kayal was born and raised in Guwahati, India.

## Neeraj Kayal's Published Works

### Published Works

- PRIMES is in P (2004) (1057)
- Approaching the Chasm at Depth Four (2013) (118)
- Arithmetic Circuits: A Chasm at Depth Three (2013) (107)
- Polynomial Identity Testing for Depth 3 Circuits (2006) (105)
- Blackbox Polynomial Identity Testing for Depth 3 Circuits (2009) (95)
- An exponential lower bound for the sum of powers of bounded degree polynomials (2012) (81)
- Partial Derivatives in Arithmetic Complexity and Beyond (2011) (74)
- A super-polynomial lower bound for regular arithmetic formulas (2014) (66)
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas (2014) (61)
- Arithmetic Circuits: A Chasm at Depth 3 (2016) (48)
- A branch and bound algorithm for solving the multiple-choice knapsack problem (1984) (48)
- Efficient algorithms for some special cases of the polynomial equivalence problem (2011) (43)
- Affine projections of polynomials: extended abstract (2012) (36)
- The Complexity of the Annihilating Polynomial (2009) (32)
- Reconstruction of depth-4 multilinear circuits with top fan-in 2 (2012) (29)
- An almost Cubic Lower Bound for Depth Three Arithmetic Circuits (2016) (28)
- On the size of homogeneous and of depth four formulas with low individual degree (2016) (25)
- Partial Derivatives in Arithmetic Complexity and Beyond (Foundations and Trends(R) in Theoretical Computer Science) (2011) (25)
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas (2014) (25)
- Complexity of Ring Morphism Problems (2006) (25)
- Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits (2020) (25)
- Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin (2015) (24)
- Factoring Groups Efficiently (2009) (22)
- On the ring isomorphism & automorphism problems (2005) (20)
- Affine projections of polynomials (2011) (20)
- An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin (2012) (20)
- Reconstruction of Full Rank Algebraic Branching Programs (2018) (18)
- Random arithmetic formulas can be reconstructed efficiently (2013) (18)
- On the Sum of Square Roots of Polynomials and Related Problems (2011) (17)
- Efficient Reconstruction of Random Multilinear Formulas (2011) (15)
- Algorithms for Arithmetic Circuits (2010) (15)
- Lower Bounds for Sums of Powers of Low Degree Univariates (2015) (15)
- DERANDOMIZING SOME NUMBER-THEORETIC AND ALGEBRAIC ALGORITHMS. (2006) (14)
- A Selection of Lower Bounds for Arithmetic Circuits (2014) (14)
- Reconstruction of non-degenerate homogeneous depth three circuits (2019) (14)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (2019) (13)
- Multi-k-ic Depth Three Circuit Lower Bound (2015) (13)
- Learning sums of powers of low-degree polynomials in the non-degenerate case (2020) (11)
- Solvability of a System of Bivariate Polynomial Equations over a Finite Field (2005) (10)
- Towards a deterministic polynomial-time Primality Test (2002) (8)
- PRIMES is in (2002) (8)
- Lower Bounds for Sums of Products of Low arity Polynomials (2015) (7)
- Determinant equivalence test over finite fields and over ℚ (2019) (6)
- Recognizing permutation functions in polynomial time (2005) (5)
- Errata: PRIMES is in P (2019) (5)
- Derandomizing some algebraic and number-theoretic algorithms (2006) (3)
- PROVING PRIMALITY AFTER AGRAWAL-KAYAL-SAXENA (2022) (1)
- Random Arithmetic Formulas can be Reconstructed Efficiently Full Version (2012) (1)
- Guest Column: A Paradigm for Arithmetic Circuit Lower Bounds (2018) (1)
- Arithmetic Circuit Complexity (Tutorial) (2014) (1)
- 18.703 Modern Algebra, A Quick Primality Test (2013) (0)
- Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant (2011) (0)
- Learning generalized depth-three arithmetic circuits in the non-degenerate case (2021) (0)
- Multi-k-ic Depth Three Circuit Lower Bound (2016) (0)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (2019) (0)
- Low-depth arithmetic circuit lower bounds via shifted partials (2022) (0)
- PRIMES is in P Manindra (2002) (0)
- Unexpected power of low-depth arithmetic circuits (2017) (0)
- Appendix A The complexity of CoeffSLP (2010) (0)
- n Generating Large Primes Using AKS (2005) (0)
- Math 788M: Computational Number Theory (2007) (0)

This paper list is powered by the following services:

## Other Resources About Neeraj Kayal

## What Schools Are Affiliated With Neeraj Kayal?

Neeraj Kayal is affiliated with the following schools: