Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-067 | 5th August 2021 14:05

Variety Evasive Subspace Families

RSS-Feed




Revision #1
Authors: Zeyu Guo
Accepted on: 5th August 2021 14:05
Downloads: 591
Keywords: 


Abstract:

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},\epsilon)-evasive if for every \mathcal{V}\in\mathcal{F}, all but at most \epsilon-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^{\Omega(1)}, the lower bound is superpolynomial unless d is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties.



Changes to previous version:

Slightly improved upper bound. The non-explicit construction and its analysis are also added.


Paper:

TR21-067 | 6th May 2021 20:55

Variety Evasive Subspace Families


Abstract:

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},\epsilon)-evasive if for every \mathcal{V}\in\mathcal{F}, all but at most \epsilon-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 bounded 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 lower bound for the size of k-subspace families that are evasive for degree-d varieties in a projective n-space. When n-k=\Omega(n), the lower bound is superpolynomial unless d is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties.



ISSN 1433-8092 | Imprint