2026-07-24T02:02:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14294 2024-03-06T10:53:53Z ddc:004 open_access

Variety Evasive Subspace Families Guo, Zeyu algebraic complexity dimension reduction Noether normalization polynomial identity testing pseudorandomness varieties We introduce the problem of constructing explicit variety evasive subspace families. Given a family ℱ of subvarieties of a projective or affine space, a collection ℋ of projective or affine k-subspaces is (ℱ,ε)-evasive if for every 𝒱 ∈ ℱ, all but at most ε-fraction of W ∈ ℋ intersect every irreducible component of 𝒱 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 = 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyu Guo 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.20 urn:nbn:de:0030-drops-142949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.20 eng https://creativecommons.org/licenses/by/4.0/legalcode