pith. sign in

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

An Improved Construction of Variety-Evasive Subspace Families

Robert Andrews , Abhibhav Garg This is my paper

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

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 · 300 canonical work pages

  1. [1]

    1997 , isbn =

    Koiran, Pascal , title =. 1997 , isbn =

    work page 1997

  2. [2]

    Journal of complexity , volume=

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

    work page 1996

  3. [3]

    Theoretical Computer Science , volume=

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

    work page 1980

  4. [4]

    Numerische Mathematik , volume=

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

    work page 1998

  5. [5]

    The American Mathematical Monthly , volume=

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

    work page 1958

  6. [6]

    2013 , publisher=

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

    work page 2013

  7. [7]

    1990 , note =

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

    work page doi:10.1016/s0747-7171(08)80012-0 1990

  8. [8]

    Bulletin of the American Mathematical Society , year =

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

    work page

  9. [9]

    Vadhan , title =

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

    work page

  10. [10]

    Forbes , title =

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

    work page 2015

  11. [11]

    Forbes , title =

    Michael A. Forbes , title =

    work page

  12. [12]

    Forbes and Amir Shpilka , title =

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

    work page 2015

  13. [13]

    Hardness vs Randomness for Bounded Depth Arithmetic Circuits , booktitle =

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

    work page 2018

  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 =

    work page doi:10.4086/toc.2019.v015a013 2019

  15. [15]

    2019 , note =

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

    work page 2019

  16. [16]

    2009 , url =

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

    work page 2009

  17. [17]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/s00037-016-0130-2 2016

  18. [18]

    30th Conference on Computational Complexity,

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

    work page 2015

  19. [19]

    2018 , url =

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

    work page 2018

  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 =

    work page doi:10.1145/3365667 2020

  21. [21]

    Computational Complexity , volume =

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

    work page 2015

  22. [22]

    1991 , url =

    Noam Nisan , title =. 1991 , url =

    work page 1991

  23. [23]

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

    work page 2012

  24. [24]

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

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

    work page 2015

  25. [25]

    2018 , url =

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

    work page 2018

  26. [26]

    2022 , issue_date =

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

    work page doi:10.1145/3510359 2022

  27. [27]

    Stanley , title =

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

    work page 1999

  28. [28]

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

    work page 1985

  29. [29]

    Trager , title =

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

    work page 1990

  30. [30]

    Advances in Computing Research , volume =

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

    work page

  31. [31]

    Proceedings of the 19th Annual

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

    work page doi:10.1145/28395.28443 1987

  32. [32]

    DeMillo and Richard J

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

    work page 1978

  33. [33]

    Schwartz , title =

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

    work page 1980

  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 =

    work page 1979

  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 =

    work page

  36. [36]

    Bulletin of the

    Nitin Saxena , title =. Bulletin of the

    work page

  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 =

    work page 2010

  38. [38]

    Forbes and Amir Shpilka , title =

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

    work page 2013

  39. [39]

    Computational Complexity , volume =

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

    work page doi:10.1007/s00037-004-0182-6 2004

  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 =

    work page doi:10.1109/focs.2019.00018 2019

  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 =

    work page doi:10.1145/3170709 2018

  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 =

    work page doi:10.1145/2591796.2591816 2014

  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 =

    work page doi:10.1007/s00037-016-0141-z 2017

  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 =

    work page doi:10.4086/toc.2017.v013a002 2017

  45. [45]

    2015 , url =

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

    work page doi:10.1137/140975103 2015

  46. [46]

    2013 , url =

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

    work page doi:10.1145/2488608.2488649 2013

  47. [47]

    Computational Complexity , volume =

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

    work page doi:10.1007/s00037-005-0188-8 2005

  48. [48]

    Journal of Algebraic Combinatorics , volume =

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

    work page 2015

  49. [49]

    2008 , url =

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

    work page doi:10.1007/978-3-540-70575-8 2008

  50. [50]

    Linear Algebra and its Applications , volume =

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

    work page 2016

  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 =

    work page 1994

  52. [52]

    , TITLE =

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

    work page 1990

  53. [53]

    2010 , MRCLASS =

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

    work page doi:10.1007/978-3-642-14165-2_35 2010

  54. [54]

    2017 , MRCLASS =

    Volkovich, Ilya , TITLE =. 2017 , MRCLASS =

    work page 2017

  55. [55]

    2020 , volume =

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

    work page 2020

  56. [56]

    Computational Complexity , doi =

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

    work page

  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 =

    work page doi:10.4230/lipics.approx/random.2020.4 2020

  58. [58]

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

    work page 2020

  59. [59]

    2015 , volume =

    Ilya Volkovich , title =. 2015 , volume =

    work page 2015

  60. [60]

    2021 , volume =

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

    work page 2021

  61. [61]

    2019 , MRCLASS =

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

    work page 2019

  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 =

    work page doi:10.1073/pnas.1901272116 2019

  63. [63]

    Invariant theory,

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

    work page 1978

  64. [64]

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

    work page 1980

  65. [65]

    Theory Comput

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

    work page doi:10.4086/toc.2006.v002a006 2006

  66. [66]

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

    work page doi:10.1137/070707932 2008

  67. [67]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/s00037-009-0270-8 2009

  68. [68]

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

    work page doi:10.1145/1502793.1502797 2009

  69. [69]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/bf01294256 1997

  70. [70]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/pl00001609 2001

  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 =

    work page doi:10.1016/0304-3975(83)90110-x 1983

  72. [72]

    Numerische Mathematik , VOLUME =

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

    work page doi:10.1007/bf01436566 1973

  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 =

    work page doi:10.1007/s00493-019-4009-0 2020

  74. [74]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/s00037-019-00186-3 2019

  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 =

    work page doi:10.4230/lipics.ccc.2020.2 2020

  76. [76]

    , TITLE =

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

    work page doi:10.1137/0214050 1985

  77. [77]

    2014 , isbn =

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

    work page doi:10.1145/2591796.2591847 2014

  78. [78]

    European J

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

    work page doi:10.1016/s0195-6698(84)80004-9 1984

  79. [79]

    Computational Complexity , VOLUME =

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

    work page doi:10.1007/bf01270384 1997

  80. [80]

    Theory of Computing , VOLUME =

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

    work page doi:10.4086/toc.2010.v006a007 2010

Showing first 80 references.