2026-09-10T09:44:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27773 2026-09-09T12:19:38Z ddc:004 open_access

An Improved Construction of Variety-Evasive Subspace Families Andrews, Robert Garg, Abhibhav algebraic complexity pseudorandomness varieties variety-evasive subspaces Chow forms We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both hitting sets and lossless rank condensers. Roughly speaking, a variety-evasive subspace family ℋ is a collection of subspaces such that for every algebraic variety V in a fixed family ℱ, there is some subspace W ∈ ℋ that is in general position with respect to V. We give an explicit construction of a subspace families that evade all degree-d varieties in an n-dimensional affine or projective space. Our construction improves on the size of the variety-evasive subspace families constructed by Guo and, for varieties of degree n^{1 + Ω(1)}, is polynomially close to Guo’s lower bound on the size of any such variety-evasive subspace family. Our variety-evasive subspace families rely on an improved construction of hitting sets for Chow forms of algebraic varieties. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Andrews and Abhibhav Garg 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.56 urn:nbn:de:0030-drops-277738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.56 eng https://creativecommons.org/licenses/by/4.0/legalcode