pith. sign in

arxiv: 2605.05621 · v1 · submitted 2026-05-07 · 💻 cs.CC

An Improved Construction of Variety-Evasive Subspace Families

Pith reviewed 2026-05-08 03:31 UTC · model grok-4.3

classification 💻 cs.CC
keywords variety-evasive subspace familiesexplicit constructionsChow formshitting setsalgebraic varietiespseudorandomnessaffine spaceprojective space
0
0 comments X p. Extension

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.

This paper gives an explicit construction of a family of subspaces such that for every degree-d algebraic variety in n-dimensional space, some subspace in the family is in general position with the variety. The construction improves the size of previous explicit constructions by Guo. For varieties whose degree is at least roughly n to the power 1 plus a positive constant, the size is within a polynomial factor of the known lower bound. A reader would care because these families generalize hitting sets and rank condensers, which are tools for derandomizing algorithms.

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 are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

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)
  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)
  1. [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.
  2. [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

1 responses · 0 unresolved

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
  1. 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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of an improved explicit hitting-set construction for Chow forms whose parameters translate into the stated subspace-family sizes; this is treated as a domain assumption rather than derived from first principles in the abstract.

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
    Abstract states that the subspace-family construction relies on such hitting sets; no independent derivation or prior reference is given in the provided text.

pith-pipeline@v0.9.0 · 5468 in / 1375 out tokens · 58093 ms · 2026-05-08T03:31:00.649666+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 113 canonical work pages

  1. [1]

    1997 , isbn =

    Koiran, Pascal , title =. 1997 , isbn =

  2. [2]

    Journal of complexity , volume=

    Hilbert's Nullstellensatz is in the polynomial hierarchy , author=. Journal of complexity , volume=. 1996 , publisher=

  3. [3]

    Theoretical Computer Science , volume=

    Lower bounds for polynomials with algebraic coefficients , author=. Theoretical Computer Science , volume=. 1980 , publisher=

  4. [4]

    Numerische Mathematik , volume=

    Vandermonde matrices on integer nodes , author=. Numerische Mathematik , volume=. 1998 , publisher=

  5. [5]

    The American Mathematical Monthly , volume=

    Inverses of Vandermonde matrices , author=. The American Mathematical Monthly , volume=. 1958 , publisher=

  6. [6]

    2013 , publisher=

    Commutative algebra: with a view toward algebraic geometry , author=. 2013 , publisher=

  7. [7]

    1990 , note =

    Generalised characteristic polynomials , journal =. 1990 , note =. doi:https://doi.org/10.1016/S0747-7171(08)80012-0 , url =

  8. [8]

    Bulletin of the American Mathematical Society , year =

    Expander graphs and their applications , author =. Bulletin of the American Mathematical Society , year =

  9. [9]

    Vadhan , title =

    Salil P. Vadhan , title =. Foundations and Trends in Theoretical Computer Science , volume =

  10. [10]

    Forbes , title =

    Michael A. Forbes , title =. 2015 , url =

  11. [11]

    Forbes , title =

    Michael A. Forbes , title =

  12. [12]

    Forbes and Amir Shpilka , title =

    Michael A. Forbes and Amir Shpilka , title =. 2015 , url =

  13. [13]

    Hardness vs Randomness for Bounded Depth Arithmetic Circuits , booktitle =

    Chi. Hardness vs Randomness for Bounded Depth Arithmetic Circuits , booktitle =. 2018 , url =

  14. [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. [15]

    2019 , note =

    Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam , title =. 2019 , note =

  16. [16]

    2009 , url =

    Zeev Dvir and Amir Shpilka and Amir Yehudayoff , title =. 2009 , url =

  17. [17]

    Computational Complexity , VOLUME =

    Oliveira, Rafael , TITLE =. Computational Complexity , VOLUME =. 2016 , NUMBER =. doi:10.1007/s00037-016-0130-2 , addendum =

  18. [18]

    30th Conference on Computational Complexity,

    Rafael Mendes de Oliveira , title =. 30th Conference on Computational Complexity,. 2015 , url =

  19. [19]

    2018 , url =

    Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich , title =. 2018 , url =

  20. [20]

    Journal of the

    Bhargava, Vishwas and Saraf, Shubhangi and Volkovich, Ilya , title =. Journal of the. 2020 , issue_date =. doi:10.1145/3365667 , note =

  21. [21]

    Computational Complexity , volume =

    Swastik Kopparty and Shubhangi Saraf and Amir Shpilka , title =. Computational Complexity , volume =. 2015 , url =

  22. [22]

    1991 , url =

    Noam Nisan , title =. 1991 , url =

  23. [23]

    Lubotzky, Alexander , TITLE =. Bull. Amer. Math. Soc. (N.S.) , FJOURNAL =. 2012 , NUMBER =

  24. [24]

    Cox and John Little and Donal O'Shea , title =

    David A. Cox and John Little and Donal O'Shea , title =. 2015 , isbn =

  25. [25]

    2018 , url =

    Pranjal Dutta and Nitin Saxena and Amit Sinhababu , title =. 2018 , url =

  26. [26]

    2022 , issue_date =

    Dutta, Pranjal and Saxena, Nitin and Sinhababu, Amit , title =. 2022 , issue_date =. doi:10.1145/3510359 , journal =

  27. [27]

    Stanley , title =

    Richard P. Stanley , title =. 1999 , publisher =

  28. [28]

    Joachim von zur Gathen and Erich Kaltofen , title =. J. Comput. Syst. Sci. , volume =. 1985 , url =

  29. [29]

    Trager , title =

    Erich Kaltofen and Barry M. Trager , title =. J. Symb. Comput. , volume =. 1990 , url =

  30. [30]

    Advances in Computing Research , volume =

    Erich Kaltofen , title =. Advances in Computing Research , volume =

  31. [31]

    Proceedings of the 19th Annual

    Erich Kaltofen , title =. Proceedings of the 19th Annual. 1987 , url =. doi:10.1145/28395.28443 , timestamp =

  32. [32]

    DeMillo and Richard J

    Richard A. DeMillo and Richard J. Lipton , title =. Inf. Process. Lett. , volume =. 1978 , url =

  33. [33]

    Schwartz , title =

    Jacob T. Schwartz , title =. J. 1980 , url =

  34. [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 =

  35. [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. [36]

    Bulletin of the

    Nitin Saxena , title =. Bulletin of the

  37. [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 =

  38. [38]

    Forbes and Amir Shpilka , title =

    Michael A. Forbes and Amir Shpilka , title =. 2013 , url =

  39. [39]

    Computational Complexity , volume =

    Valentine Kabanets and Russell Impagliazzo , title =. Computational Complexity , volume =. 2004 , url =. doi:10.1007/s00037-004-0182-6 , timestamp =

  40. [40]

    In: Proceedings of the 41st International Conference on Software Engi- neering: Software Engineering in Practice

    Zeyu Guo and Mrinal Kumar and Ramprasad Saptharishi and Noam Solomon , title =. 2019 , url =. doi:10.1109/FOCS.2019.00018 , timestamp =

  41. [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. [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. [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. [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. [45]

    2015 , url =

    Manindra Agrawal and Rohit Gurjar and Arpita Korwar and Nitin Saxena , title =. 2015 , url =. doi:10.1137/140975103 , timestamp =

  46. [46]

    2013 , url =

    Manindra Agrawal and Chandan Saha and Nitin Saxena , title =. 2013 , url =. doi:10.1145/2488608.2488649 , timestamp =

  47. [47]

    Computational Complexity , volume =

    Ran Raz and Amir Shpilka , title =. Computational Complexity , volume =. 2005 , url =. doi:10.1007/s00037-005-0188-8 , timestamp =

  48. [48]

    Journal of Algebraic Combinatorics , volume =

    Zach Teitler and Alexander Woo , title =. Journal of Algebraic Combinatorics , volume =. 2015 , pages=

  49. [49]

    2008 , url =

    Nitin Saxena , title =. 2008 , url =. doi:10.1007/978-3-540-70575-8\_6 , biburl =

  50. [50]

    Linear Algebra and its Applications , volume =

    Hwangrae Lee , title =. Linear Algebra and its Applications , volume =. 2016 , pages =

  51. [51]

    Sums of Like Powers of Multivariate Linear Forms , volume =

    Ismor Fischer , journal =. Sums of Like Powers of Multivariate Linear Forms , volume =. 1994 , ISSN =

  52. [52]

    , TITLE =

    Bourbaki, N. , TITLE =. 1990 , PAGES =

  53. [53]

    2010 , MRCLASS =

    Shpilka, Amir and Volkovich, Ilya , TITLE =. 2010 , MRCLASS =. doi:10.1007/978-3-642-14165-2_35 , URL =

  54. [54]

    2017 , MRCLASS =

    Volkovich, Ilya , TITLE =. 2017 , MRCLASS =

  55. [55]

    2020 , volume =

    Amit Sinhababu and Thomas Thierauf , title =. 2020 , volume =

  56. [56]

    Computational Complexity , doi =

    Amit Sinhababu and Thomas Thierauf , title =. Computational Complexity , doi =

  57. [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. [58]

    Robert Andrews , title =. 35th. 2020 , series =

  59. [59]

    2015 , volume =

    Ilya Volkovich , title =. 2015 , volume =

  60. [60]

    2021 , volume =

    Pranjal Dutta and Nitin Saxena and Thomas Thierauf , title =. 2021 , volume =

  61. [61]

    2019 , MRCLASS =

    Kumar, Mrinal and Saptharishi, Ramprasad and Tengse, Anamay , TITLE =. 2019 , MRCLASS =

  62. [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. [63]

    Invariant theory,

    D\'. Invariant theory,. Advances in Math. , FJOURNAL =. 1978 , NUMBER =

  64. [64]

    de Concini, Corrado and Eisenbud, David and Procesi, Claudio , TITLE =. Invent. Math. , FJOURNAL =. 1980 , NUMBER =

  65. [65]

    Theory Comput

    Raz, Ran , TITLE =. Theory Comput. , FJOURNAL =. 2006 , PAGES =. doi:10.4086/toc.2006.v002a006 , URL =

  66. [66]

    Raz, Ran and Shpilka, Amir and Yehudayoff, Amir , TITLE =. SIAM J. Comput. , FJOURNAL =. 2008 , NUMBER =. doi:10.1137/070707932 , URL =

  67. [67]

    Computational Complexity , VOLUME =

    Raz, Ran and Yehudayoff, Amir , TITLE =. Computational Complexity , VOLUME =. 2009 , NUMBER =. doi:10.1007/s00037-009-0270-8 , URL =

  68. [68]

    Raz, Ran , TITLE =. J. ACM , FJOURNAL =. 2009 , NUMBER =. doi:10.1145/1502793.1502797 , URL =

  69. [69]

    Computational Complexity , VOLUME =

    Nisan, Noam and Wigderson, Avi , TITLE =. Computational Complexity , VOLUME =. 1997 , NUMBER =. doi:10.1007/BF01294256 , URL =

  70. [70]

    Computational Complexity , VOLUME =

    Shpilka, Amir and Wigderson, Avi , TITLE =. Computational Complexity , VOLUME =. 2001 , NUMBER =. doi:10.1007/PL00001609 , URL =

  71. [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. [72]

    Numerische Mathematik , VOLUME =

    Strassen, Volker , TITLE =. Numerische Mathematik , VOLUME =. 1973 , PAGES =. doi:10.1007/BF01436566 , URL =

  73. [73]

    Combinatorica , FJOURNAL =

    Alon, Noga and Kumar, Mrinal and Volk, Ben Lee , TITLE =. Combinatorica , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s00493-019-4009-0 , URL =

  74. [74]

    Computational Complexity , VOLUME =

    Kumar, Mrinal , TITLE =. Computational Complexity , VOLUME =. 2019 , NUMBER =. doi:10.1007/s00037-019-00186-3 , URL =

  75. [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. [76]

    , TITLE =

    Kalorkoti, Kyriakos A. , TITLE =. SIAM J. Comput. , FJOURNAL =. 1985 , NUMBER =. doi:10.1137/0214050 , URL =

  77. [77]

    2014 , isbn =

    Kayal, Neeraj and Saha, Chandan and Saptharishi, Ramprasad , title =. 2014 , isbn =. doi:10.1145/2591796.2591847 , booktitle =

  78. [78]

    European J

    Clausen, Michael , TITLE =. European J. Combin. , FJOURNAL =. 1984 , NUMBER =. doi:10.1016/S0195-6698(84)80004-9 , URL =

  79. [79]

    Computational Complexity , VOLUME =

    Shoup, Victor and Smolensky, Roman , TITLE =. Computational Complexity , VOLUME =. 1997 , NUMBER =. doi:10.1007/BF01270384 , URL =

  80. [80]

    Theory of Computing , VOLUME =

    Raz, Ran , TITLE =. Theory of Computing , VOLUME =. 2010 , PAGES =. doi:10.4086/toc.2010.v006a007 , URL =

Showing first 80 references.