They provided the first unconditional deterministic algorithm to test an n-digit number for primality in a time that has been proven to be polynomial in n.[2] This research work came out as a part of his undergraduate study.

He received his PhD from the Department of Computer Science and Engineering of the same institute in 2006 with the Dissertation titled "Morphisms of Rings and Applications to Complexity".

He was appointed at the Centrum Wiskunde & Informatica (CWI) starting as a postdoc researcher from September 2006 onwards.

[5][better source needed] Saxena was awarded the 2018 Shanti Swarup Bhatnagar Prize for his work in Algebraic Complexity Theory.

One of the youngest awardees, Saxena’s research interests include Computational Complexity and Algebraic Geometry.