Abhibhav Garg

abhibhav dot garg at uwaterloo dot ca

I am a postdoc at the University of Waterloo, hosted by Éric Schost and Rafael Oliveira. From 2021 to 2025 I was a graduate student at the University of Waterloo, where I was advised by Rafael Oliveira. From 2015 to 2020 I was a student in the computer science department of IIT Kanpur where I got a dual B.Tech and M.Tech degree. My advisor was Nitin Saxena.

I am interested in complexity theory, in particular in algebraic complexity. I am also interested in computational algebra and number theory.

Research

• Hilbert's Nullstellensatz is in the Counting Hierarchy
  with Robert Andrews and Éric Schost
  [arXiv | ECCC]
  
• Rank Bounds and PIT for Σ³ΠΣΠ^d circuits via a non-linear Edelstein-Kelly theorem
  with Rafael Oliveira and Akash Kumar Sengupta
  FOCS 2025
  [arXiv | ECCC]
  
• An exposition of recent list-size bounds of FRS Codes
  with Prahladh Harsha and Mrinal Kumar and Ramprasad Saptharishi and Ashutosh Shankar
  [arXiv | ECCC]
  
• Primes via Zeros: interactive proofs for testing primality of natural classes of ideals
  with Rafael Oliveira and Nitin Saxena
  STOC 2025
  [arXiv | ECCC | YouTube]
  
• Uniform Bounds on Product Sylvester–Gallai Configurations
  with Rafael Oliveira and Akash Kumar Sengupta
  SoCG 2025
  [ECCC]
  
• Radical Sylvester-Gallai Theorem for Tuples of Quadratics
  with Rafael Oliveira and Shir Peleg and Akash Kumar Sengupta
  CCC 2023
  [ECCC]
  
• Robust radical Sylvester–Gallai theorem for quadratics
  with Rafael Oliveira and Akash Kumar Sengupta
  SoCG 2022
  [arXiv]
  
• Special-case algorithms for blackbox radical membership, Nullstellensatz and transcendence degree
  with Nitin Saxena
  ISSAC 2020
  [arXiv | YouTube]
  

Miscellaneous

• Ph.D. thesis:
  Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing
• Master's thesis:
  Special case algorithms for Nullstellensatz and transcendence degree
• A multivariate folded wronskian

I help maintain the website of the Algorithms and Complexity group at Waterloo. The group organises a weekly seminar.

I used to co-organise the special interest group on theoretical aspects of computer science at IIT Kanpur. If you are interested in attending the talks, you can sign up to the mailing list and/or check the website. The latter includes links to the recordings of some of the talks.