Source author record

Abhibhav Garg

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Computational Geometry Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.