Source author record

Abhibhav Garg

Abhibhav Garg appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

2works
4topics
3close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

2 published item(s)

preprint2022arXiv

Robust Radical Sylvester-Gallai Theorem for Quadratics

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20]. More precisely, given a parameter $0 < δ\leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a $(δ, 2)$-radical Sylvester-Gallai configuration if for any polynomial $F_i \in \mathcal{F}$, there exist $δ(|\mathcal{F}| -1)$ polynomials $F_j$ such that $|\mathrm{rad}(F_i, F_j) \cap \mathcal{F}| \geq 3$, that is, the radical of $F_i, F_j$ contains a third polynomial in the set. In this work, we prove that any $(δ, 2)$-radical Sylvester-Gallai configuration $\mathcal{F}$ must be of low dimension: that is $$\dim \mathrm{span}(\mathcal{F}) = \mathrm{poly}(1/δ).$$

preprint2020arXiv

Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree

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 due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, and improved bounds, could be given, when the transcendence degree $r$ of the input polynomials is smaller than the number of variables $n$. If $d$ is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around $d^r$ time. The prior best was $> d^n$ time (always, $d^n\ge d^r$). Also, we significantly improve effective Nullstellensatz degree-bound, when $r\ll n$. Structurally, our proof shows that these problems reduce to the case of $r+1$ polynomials of transcendence degree $\ge r$. This input instance (corresponding to none or a unique annihilator) is at the core of HN's hardness. Our proof methods invoke basic algebraic-geometry.