An Improved Construction of Variety-Evasive Subspace Families
Pith reviewed 2026-05-08 03:31 UTC · model grok-4.3
The pith
An explicit construction yields smaller variety-evasive subspace families that nearly match lower bounds for high-degree varieties.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We give an explicit construction of 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)}, comes within a polynomial factor of 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.
What carries the argument
Improved explicit hitting sets for Chow forms of algebraic varieties, which enable a reduction that produces smaller subspace families intersecting every degree-d variety in general position.
If this is right
- Explicit variety-evasive families now exist with improved size bounds for any fixed degree d.
- For varieties of degree at least n to a power strictly larger than 1, the explicit size comes within a polynomial factor of the information-theoretic lower bound.
- The same construction applies uniformly to both affine and projective spaces.
- The improvement supplies better explicit hitting sets for Chow forms as an intermediate object.
Where Pith is reading between the lines
- These smaller families may support more efficient explicit constructions for algebraic pseudorandomness primitives beyond subspaces.
- The approach could be tested computationally on small values of n and d to check whether the general-position condition holds in practice.
- If the hitting-set parameters can be strengthened further, the remaining polynomial gap to the lower bound might disappear.
Load-bearing premise
The size improvement requires an explicit hitting set for Chow forms that meets the specific parameters needed to produce the claimed subspace family sizes.
What would settle it
The claim would be falsified by an explicit degree-d variety in n-space for which no subspace from the constructed family lies in general position, or by a demonstration that no hitting set for Chow forms achieves the required parameters.
read the original abstract
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 $\mathcal{H}$ is a collection of subspaces such that for every algebraic variety $V$ in a fixed family $\mathcal{F}$, there is some subspace $W \in \mathcal{H}$ 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 + \Omega(1)}$, comes within a polynomial factor of 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims an explicit construction of variety-evasive subspace families that evade all degree-d varieties in an n-dimensional affine or projective space. The construction improves the size bounds of Guo's prior families and, for d = n^{1+Ω(1)}, comes within a polynomial factor of Guo's lower bound; it is obtained by reducing to an improved explicit hitting set for Chow forms of algebraic varieties.
Significance. If the parameter calculations hold, the result strengthens explicit constructions in algebraic pseudorandomness by generalizing hitting sets and lossless rank condensers, with the near-optimality for high-degree varieties constituting a notable advance over prior work.
major comments (1)
- [Main construction and parameter analysis (reduction from subspace families to Chow-form hitting sets)] The central size improvement and the polynomial-factor proximity to the lower bound both require that the new Chow-form hitting-set size (as a function of n and d) is sufficiently smaller than prior constructions after accounting for reduction overhead. The manuscript should include an explicit calculation (e.g., in the proof of the main theorem) showing that the hitting-set parameters suffice for the claimed bounds when d = n^{1+Ω(1)}.
minor comments (2)
- [Abstract and §1] The abstract states the result for both affine and projective spaces; the body should explicitly state the base field and any differences in the construction or bounds between the two settings.
- [Notation and comparison paragraphs] Notation for the subspace family size |H| and the hitting-set size should be introduced once and used consistently when comparing to Guo's bounds and the lower bound.
Simulated Author's Rebuttal
We thank the referee for the careful reading, positive assessment of the significance, and recommendation for minor revision. We address the major comment below.
read point-by-point responses
-
Referee: [Main construction and parameter analysis (reduction from subspace families to Chow-form hitting sets)] The central size improvement and the polynomial-factor proximity to the lower bound both require that the new Chow-form hitting-set size (as a function of n and d) is sufficiently smaller than prior constructions after accounting for reduction overhead. The manuscript should include an explicit calculation (e.g., in the proof of the main theorem) showing that the hitting-set parameters suffice for the claimed bounds when d = n^{1+Ω(1)}.
Authors: We agree that an explicit parameter calculation will improve clarity. In the revised manuscript we will add a self-contained calculation (in the proof of the main theorem) that starts from the size of our new Chow-form hitting set, accounts for the overhead of the reduction to variety-evasive subspace families, and verifies that the resulting family size improves on Guo's construction and lies within a polynomial factor of the lower bound precisely when d = n^{1+Ω(1)}. This calculation uses only the parameter regimes already established in the paper and confirms the claimed asymptotic statements. revision: yes
Circularity Check
No circularity: explicit construction via independent hitting-set primitive
full rationale
The paper presents an explicit construction of variety-evasive subspace families that reduces the problem to an improved explicit hitting set for Chow forms. This reduction is a standard algorithmic reduction rather than a self-definition or fitted-parameter renaming; the hitting-set construction supplies concrete parameters that are then plugged into the subspace-family size bound. No equation equates the output size to the input size by construction, no self-citation is invoked as a uniqueness theorem, and the claimed improvement over Guo is obtained by substituting a smaller hitting-set size into an existing reduction. The derivation chain therefore remains non-circular and externally falsifiable via the explicitness of both the hitting set and the final family.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Improved explicit hitting sets for Chow forms exist with size and degree parameters sufficient to produce the claimed variety-evasive family sizes
Reference graph
Works this paper leans on
-
[1]
1997 , isbn =
Koiran, Pascal , title =. 1997 , isbn =
1997
-
[2]
Journal of complexity , volume=
Hilbert's Nullstellensatz is in the polynomial hierarchy , author=. Journal of complexity , volume=. 1996 , publisher=
1996
-
[3]
Theoretical Computer Science , volume=
Lower bounds for polynomials with algebraic coefficients , author=. Theoretical Computer Science , volume=. 1980 , publisher=
1980
-
[4]
Numerische Mathematik , volume=
Vandermonde matrices on integer nodes , author=. Numerische Mathematik , volume=. 1998 , publisher=
1998
-
[5]
The American Mathematical Monthly , volume=
Inverses of Vandermonde matrices , author=. The American Mathematical Monthly , volume=. 1958 , publisher=
1958
-
[6]
2013 , publisher=
Commutative algebra: with a view toward algebraic geometry , author=. 2013 , publisher=
2013
-
[7]
Generalised characteristic polynomials , journal =. 1990 , note =. doi:https://doi.org/10.1016/S0747-7171(08)80012-0 , url =
-
[8]
Bulletin of the American Mathematical Society , year =
Expander graphs and their applications , author =. Bulletin of the American Mathematical Society , year =
-
[9]
Vadhan , title =
Salil P. Vadhan , title =. Foundations and Trends in Theoretical Computer Science , volume =
-
[10]
Forbes , title =
Michael A. Forbes , title =. 2015 , url =
2015
-
[11]
Forbes , title =
Michael A. Forbes , title =
-
[12]
Forbes and Amir Shpilka , title =
Michael A. Forbes and Amir Shpilka , title =. 2015 , url =
2015
-
[13]
Hardness vs Randomness for Bounded Depth Arithmetic Circuits , booktitle =
Chi. Hardness vs Randomness for Bounded Depth Arithmetic Circuits , booktitle =. 2018 , url =
2018
-
[14]
Theory of Computing , volume =
Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam , title =. Theory of Computing , volume =. 2019 , pages =. doi:10.4086/toc.2019.v015a013 , publisher =
-
[15]
2019 , note =
Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam , title =. 2019 , note =
2019
-
[16]
2009 , url =
Zeev Dvir and Amir Shpilka and Amir Yehudayoff , title =. 2009 , url =
2009
-
[17]
Computational Complexity , VOLUME =
Oliveira, Rafael , TITLE =. Computational Complexity , VOLUME =. 2016 , NUMBER =. doi:10.1007/s00037-016-0130-2 , addendum =
-
[18]
30th Conference on Computational Complexity,
Rafael Mendes de Oliveira , title =. 30th Conference on Computational Complexity,. 2015 , url =
2015
-
[19]
2018 , url =
Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich , title =. 2018 , url =
2018
-
[20]
Bhargava, Vishwas and Saraf, Shubhangi and Volkovich, Ilya , title =. Journal of the. 2020 , issue_date =. doi:10.1145/3365667 , note =
-
[21]
Computational Complexity , volume =
Swastik Kopparty and Shubhangi Saraf and Amir Shpilka , title =. Computational Complexity , volume =. 2015 , url =
2015
-
[22]
1991 , url =
Noam Nisan , title =. 1991 , url =
1991
-
[23]
Lubotzky, Alexander , TITLE =. Bull. Amer. Math. Soc. (N.S.) , FJOURNAL =. 2012 , NUMBER =
2012
-
[24]
Cox and John Little and Donal O'Shea , title =
David A. Cox and John Little and Donal O'Shea , title =. 2015 , isbn =
2015
-
[25]
2018 , url =
Pranjal Dutta and Nitin Saxena and Amit Sinhababu , title =. 2018 , url =
2018
-
[26]
Dutta, Pranjal and Saxena, Nitin and Sinhababu, Amit , title =. 2022 , issue_date =. doi:10.1145/3510359 , journal =
-
[27]
Stanley , title =
Richard P. Stanley , title =. 1999 , publisher =
1999
-
[28]
Joachim von zur Gathen and Erich Kaltofen , title =. J. Comput. Syst. Sci. , volume =. 1985 , url =
1985
-
[29]
Trager , title =
Erich Kaltofen and Barry M. Trager , title =. J. Symb. Comput. , volume =. 1990 , url =
1990
-
[30]
Advances in Computing Research , volume =
Erich Kaltofen , title =. Advances in Computing Research , volume =
-
[31]
Proceedings of the 19th Annual
Erich Kaltofen , title =. Proceedings of the 19th Annual. 1987 , url =. doi:10.1145/28395.28443 , timestamp =
-
[32]
DeMillo and Richard J
Richard A. DeMillo and Richard J. Lipton , title =. Inf. Process. Lett. , volume =. 1978 , url =
1978
-
[33]
Schwartz , title =
Jacob T. Schwartz , title =. J. 1980 , url =
1980
-
[34]
Proceedings of the International Symposium on Symbolic and Algebraic Computation,
Richard Zippel , title =. Proceedings of the International Symposium on Symbolic and Algebraic Computation,. 1979 , url =
1979
-
[35]
Proceedings of the Workshop celebrating Somenath Biswas' 60th Birthday , pages =
Nitin Saxena , title =. Proceedings of the Workshop celebrating Somenath Biswas' 60th Birthday , pages =
-
[36]
Bulletin of the
Nitin Saxena , title =. Bulletin of the
-
[37]
Foundations and Trends in Theoretical Computer Science , volume =
Amir Shpilka and Amir Yehudayoff , title =. Foundations and Trends in Theoretical Computer Science , volume =. 2010 , url =
2010
-
[38]
Forbes and Amir Shpilka , title =
Michael A. Forbes and Amir Shpilka , title =. 2013 , url =
2013
-
[39]
Computational Complexity , volume =
Valentine Kabanets and Russell Impagliazzo , title =. Computational Complexity , volume =. 2004 , url =. doi:10.1007/s00037-004-0182-6 , timestamp =
-
[40]
Zeyu Guo and Mrinal Kumar and Ramprasad Saptharishi and Noam Solomon , title =. 2019 , url =. doi:10.1109/FOCS.2019.00018 , timestamp =
-
[41]
and Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee , title =
Anderson, Matthew and Forbes, Michael A. and Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee , title =. 2018 , publisher =. doi:10.1145/3170709 , journal =
-
[42]
Forbes and Ramprasad Saptharishi and Amir Shpilka , title =
Michael A. Forbes and Ramprasad Saptharishi and Amir Shpilka , title =. 2014 , url =. doi:10.1145/2591796.2591816 , timestamp =
-
[43]
Computational Complexity , volume =
Rohit Gurjar and Arpita Korwar and Nitin Saxena and Thomas Thierauf , title =. Computational Complexity , volume =. 2017 , url =. doi:10.1007/s00037-016-0141-z , timestamp =
-
[44]
Theory of Computing , volume =
Rohit Gurjar and Arpita Korwar and Nitin Saxena , title =. Theory of Computing , volume =. 2017 , url =. doi:10.4086/toc.2017.v013a002 , timestamp =
-
[45]
Manindra Agrawal and Rohit Gurjar and Arpita Korwar and Nitin Saxena , title =. 2015 , url =. doi:10.1137/140975103 , timestamp =
-
[46]
Manindra Agrawal and Chandan Saha and Nitin Saxena , title =. 2013 , url =. doi:10.1145/2488608.2488649 , timestamp =
-
[47]
Computational Complexity , volume =
Ran Raz and Amir Shpilka , title =. Computational Complexity , volume =. 2005 , url =. doi:10.1007/s00037-005-0188-8 , timestamp =
-
[48]
Journal of Algebraic Combinatorics , volume =
Zach Teitler and Alexander Woo , title =. Journal of Algebraic Combinatorics , volume =. 2015 , pages=
2015
-
[49]
Nitin Saxena , title =. 2008 , url =. doi:10.1007/978-3-540-70575-8\_6 , biburl =
-
[50]
Linear Algebra and its Applications , volume =
Hwangrae Lee , title =. Linear Algebra and its Applications , volume =. 2016 , pages =
2016
-
[51]
Sums of Like Powers of Multivariate Linear Forms , volume =
Ismor Fischer , journal =. Sums of Like Powers of Multivariate Linear Forms , volume =. 1994 , ISSN =
1994
-
[52]
, TITLE =
Bourbaki, N. , TITLE =. 1990 , PAGES =
1990
-
[53]
Shpilka, Amir and Volkovich, Ilya , TITLE =. 2010 , MRCLASS =. doi:10.1007/978-3-642-14165-2_35 , URL =
-
[54]
2017 , MRCLASS =
Volkovich, Ilya , TITLE =. 2017 , MRCLASS =
2017
-
[55]
2020 , volume =
Amit Sinhababu and Thomas Thierauf , title =. 2020 , volume =
2020
-
[56]
Computational Complexity , doi =
Amit Sinhababu and Thomas Thierauf , title =. Computational Complexity , doi =
-
[57]
Approximation, Randomization, and Combinatorial Optimization
Zeyu Guo and Rohit Gurjar , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.4 , annote =
-
[58]
Robert Andrews , title =. 35th. 2020 , series =
2020
-
[59]
2015 , volume =
Ilya Volkovich , title =. 2015 , volume =
2015
-
[60]
2021 , volume =
Pranjal Dutta and Nitin Saxena and Thomas Thierauf , title =. 2021 , volume =
2021
-
[61]
2019 , MRCLASS =
Kumar, Mrinal and Saptharishi, Ramprasad and Tengse, Anamay , TITLE =. 2019 , MRCLASS =
2019
-
[62]
Agrawal, Manindra and Ghosh, Sumanta and Saxena, Nitin , TITLE =. Proc. Natl. Acad. Sci. USA , FJOURNAL =. 2019 , NUMBER =. doi:10.1073/pnas.1901272116 , addendum =
-
[63]
Invariant theory,
D\'. Invariant theory,. Advances in Math. , FJOURNAL =. 1978 , NUMBER =
1978
-
[64]
de Concini, Corrado and Eisenbud, David and Procesi, Claudio , TITLE =. Invent. Math. , FJOURNAL =. 1980 , NUMBER =
1980
-
[65]
Raz, Ran , TITLE =. Theory Comput. , FJOURNAL =. 2006 , PAGES =. doi:10.4086/toc.2006.v002a006 , URL =
-
[66]
Raz, Ran and Shpilka, Amir and Yehudayoff, Amir , TITLE =. SIAM J. Comput. , FJOURNAL =. 2008 , NUMBER =. doi:10.1137/070707932 , URL =
-
[67]
Computational Complexity , VOLUME =
Raz, Ran and Yehudayoff, Amir , TITLE =. Computational Complexity , VOLUME =. 2009 , NUMBER =. doi:10.1007/s00037-009-0270-8 , URL =
-
[68]
Raz, Ran , TITLE =. J. ACM , FJOURNAL =. 2009 , NUMBER =. doi:10.1145/1502793.1502797 , URL =
-
[69]
Computational Complexity , VOLUME =
Nisan, Noam and Wigderson, Avi , TITLE =. Computational Complexity , VOLUME =. 1997 , NUMBER =. doi:10.1007/BF01294256 , URL =
-
[70]
Computational Complexity , VOLUME =
Shpilka, Amir and Wigderson, Avi , TITLE =. Computational Complexity , VOLUME =. 2001 , NUMBER =. doi:10.1007/PL00001609 , URL =
-
[71]
Theoretical Computer Science , VOLUME =
Baur, Walter and Strassen, Volker , TITLE =. Theoretical Computer Science , VOLUME =. 1983 , NUMBER =. doi:10.1016/0304-3975(83)90110-X , URL =
-
[72]
Numerische Mathematik , VOLUME =
Strassen, Volker , TITLE =. Numerische Mathematik , VOLUME =. 1973 , PAGES =. doi:10.1007/BF01436566 , URL =
-
[73]
Alon, Noga and Kumar, Mrinal and Volk, Ben Lee , TITLE =. Combinatorica , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s00493-019-4009-0 , URL =
-
[74]
Computational Complexity , VOLUME =
Kumar, Mrinal , TITLE =. Computational Complexity , VOLUME =. 2019 , NUMBER =. doi:10.1007/s00037-019-00186-3 , URL =
-
[75]
35th Computational Complexity Conference (CCC 2020) , pages =
Prerona Chatterjee and Mrinal Kumar and Adrian She and Ben Lee Volk , title =. 35th Computational Complexity Conference (CCC 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.CCC.2020.2 , annote =
-
[76]
Kalorkoti, Kyriakos A. , TITLE =. SIAM J. Comput. , FJOURNAL =. 1985 , NUMBER =. doi:10.1137/0214050 , URL =
-
[77]
Kayal, Neeraj and Saha, Chandan and Saptharishi, Ramprasad , title =. 2014 , isbn =. doi:10.1145/2591796.2591847 , booktitle =
-
[78]
Clausen, Michael , TITLE =. European J. Combin. , FJOURNAL =. 1984 , NUMBER =. doi:10.1016/S0195-6698(84)80004-9 , URL =
-
[79]
Computational Complexity , VOLUME =
Shoup, Victor and Smolensky, Roman , TITLE =. Computational Complexity , VOLUME =. 1997 , NUMBER =. doi:10.1007/BF01270384 , URL =
-
[80]
Theory of Computing , VOLUME =
Raz, Ran , TITLE =. Theory of Computing , VOLUME =. 2010 , PAGES =. doi:10.4086/toc.2010.v006a007 , URL =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.