401 citations · 401 across the 7 of their papers we have counts for
6 papers · 1 filter
An Improved Construction of Variety-Evasive Subspace Families
Robert Andrews, Abhibhav Garg
We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both…
Hilbert's Nullstellensatz is in the Counting Hierarchy
Robert Andrews, Abhibhav Garg, Éric Schost
We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, li…
Rank Bounds and PIT for circuits via a non-linear Edelstein-Kelly theorem
Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta
We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result…
Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
Abhibhav Garg, Rafael Oliveira, Nitin Saxena
A central question in mathematics and computer science is the question of determining whether a given ideal is prime, which geometrically corresponds to the zero set of , de…
An exposition of recent list-size bounds of FRS Codes
Abhibhav Garg, Prahladh Harsha, Mrinal Kumar +2
In the last year, there have been some remarkable improvements in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes. Starting from the work on…
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree
Abhibhav Garg, Nitin Saxena
Radical membership testing, and the special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm…