Abstract
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 ksubspaces 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 blackbox polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers.
Using Chow forms, we construct explicit ksubspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine nspace. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of bounded degree in a projective or affine nspace. In another application, we obtain a simple polynomialtime blackbox PIT algorithm for depth4 arithmetic circuits with bounded top fanin and bottom fanin that are not in the SylvesterGallai configuration, improving and simplifying a result of Gupta (ECCC TR 14130).
As a complement of our explicit construction, we prove a lower bound for the size of ksubspace families that are evasive for degreed varieties in a projective nspace. When nk = n^Ω(1), the lower bound is superpolynomial unless d is bounded. The proof uses a dimensioncounting argument on Chow varieties that parametrize projective subvarieties.
BibTeX  Entry
@InProceedings{guo:LIPIcs.CCC.2021.20,
author = {Guo, Zeyu},
title = {{Variety Evasive Subspace Families}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {20:120:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14294},
URN = {urn:nbn:de:0030drops142949},
doi = {10.4230/LIPIcs.CCC.2021.20},
annote = {Keywords: algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties}
}
Keywords: 

algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties 
Collection: 

36th Computational Complexity Conference (CCC 2021) 
Issue Date: 

2021 
Date of publication: 

08.07.2021 