Variety evasive subspace families

DOI10.4230/LIPICS.CCC.2021.20MaRDI QIDQ6115376zbMATH OpenOpenAlexFDO

Authors Zeyu Guo

Publication date 12 July 2023

Full work available at URL https://arxiv.org/abs/2105.02908

zbMATH Keywords

algebraic complexitydimension reductionNoether normalizationpolynomial identity testingpseudorandomnessvarieties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: We introduce the problem of constructing explicit variety evasive subspace families. Given a family $mathcalF$ of subvarieties of a projective or affine space, a collection $mathcalH$ of projective or affine $k$-subspaces is $(mathcalF,epsilon)$-evasive if for every $mathcalVinmathcalF$, all but at most $epsilon$-fraction of $WinmathcalH$ intersect every irreducible component of $mathcalV$ 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.

Cited in

(3)

• Variety evasive sets
• Variety evasive subspace families
• Uniform bounds on product Sylvester-Gallai configurations

This page was built for publication: Variety evasive subspace families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115376)