Variety Evasive Subspace Families
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913543654211584 |
|---|---|
| author | Guo, Zeyu |
| author_facet | Guo, Zeyu |
| contents | We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},ε)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $ε$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers.
Using Chow forms, we construct explicit $k$-subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine $n$-space. As one application, we obtain a complete derandomization of Noether's normalization lemma for varieties of low degree in a projective or affine $n$-space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester-Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130).
As a complement of our explicit construction, we prove a tight lower bound for the size of $k$-subspace families that are evasive for degree-$d$ varieties in a projective $n$-space. When $n-k=n^{Ω(1)}$, the lower bound is superpolynomial unless $d$ is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_02908 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Variety Evasive Subspace Families Guo, Zeyu Computational Complexity We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},ε)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $ε$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit $k$-subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine $n$-space. As one application, we obtain a complete derandomization of Noether's normalization lemma for varieties of low degree in a projective or affine $n$-space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester-Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of $k$-subspace families that are evasive for degree-$d$ varieties in a projective $n$-space. When $n-k=n^{Ω(1)}$, the lower bound is superpolynomial unless $d$ is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties. |
| title | Variety Evasive Subspace Families |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2105.02908 |