Abstract
The problem of constructing pseudorandom generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it easier to construct pseudorandom generators, or even hitting-set generators, for polynomials \(p:\mathbb{F}^n\rightarrow\mathbb{F}\) of degree d if we are guaranteed that the polynomial vanishes on at most an \(\varepsilon > 0\) fraction of its inputs? We will specifically be interested in tiny values of \(\varepsilon\ll d/|F|\). This question was first considered by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for a particular application, and another specific setting was later studied by the third author (CCC 2017).
In this work, our main interest is a systematic study of the relaxed problem,in its general form, and we prove results that significantly improve and extend the two previously known results. Our contributions are of two types:
\( \circ \) Over fields of size \(2\le|\mathbb{F}|\le\mathrm{poly}(n)\) we show that the seed length of any hitting-set generator for polynomials of degree \(d\le n^{.49}\) that vanish on at most \(\varepsilon=|\mathbb{F}|^{-t}\) of their inputs is at least \(\Omega\left((d/t)\cdot\log(n)\right)\).
\( \circ \) Over \(\mathbb{F}_2\), we show that there exists a (non-explicit) hitting-set generator for polynomials of degree \(d\le n^{.99}\) that vanish on at most \(\varepsilon=|\mathbb{F}|^{-t}\) of their inputs with seed length \(O\left((d-t)\cdot\log(n)\right)\). We also show a polynomial-time computable hitting-set generator with seed length \(O\left( (d-t)\cdot\left(2^{d-t}+\log(n)\right) \right)\).
In addition, we prove that the problem we study is closely related to the following question: “Does there exist a small set \(S\subseteq\mathbb{F}^n\) whose degree-d closure is very large?”, where the degree-d closure of S is the variety induced by the set of degree-d polynomials that vanish on S.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Emmanuel Abbe, Amir Shpilka & Avi Wigderson (2015). Reed- Muller codes for random erasures and errors. IEEE Transactions on Information Theory 61(10), 5229–5252.
N. Alon, J. Bruck, J. Naor, M. Naor & R. M. Roth (1992). Construction of Asymptotically Good Low-rate Error-correcting Codes Through Pseudo-random Graphs. IEEE Transactions on Information Theory 38(2), 509–516.
Paul Beame, Shayan Oveis Gharan & Xin Yang (2020). On the Bias of Reed–Muller Codes over Odd Prime Fields. SIAM Journal on Discrete Mathematics 34(2), 1232–1247.
Peter Beelen & Mrinmoy Datta (2018). Generalized Hamming weights of affine Cartesian codes. Finite Fields and their Applications 51, 130–145.
Ido Ben-Eliezer, Rani Hod & Shachar Lovett (2012). Random low-degree polynomials are hard to approximate. Computational Complexity 21(1), 63–81.
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan & Salil Vadhan (2006). Robust PCPs of proximity, shorter PCPs and applications to coding. SIAM Journal of Computing 36(4), 889–974.
E. R. Berlekamp & N. J. A. Sloane (1969). Restrictions on weight distribution of Reed-Muller codes. Information and Control 14, 442– 456.
Arnab Bhattacharyya (2014). Polynomial decompositions in polynomial time. In Proc. 22nd European Symposia on Algorithms, 125–136.
Arnab Bhattacharyya, Abhishek Bhowmick & Chetan Gupta (2016). On higher-order Fourier analysis over non-prime fields. In Proc. 20th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Art. No. 23, 29.
Arnab Bhattacharyya, Pooya Hatami & Madhur Tulsiani (2015). Algorithmic regularity for polynomials and applications. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1870–1889.
Markus Bläser, Moritz Hardt & David Steurer (2008). Asymptotically Optimal Hitting Sets Against Polynomials. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part I, Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP), 345–356.
Markus Bläser & Anurag Pandey (2020). Polynomial identity testing for low degree polynomials with optimal randomness. In Proc. 24th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Art. No. 8, 13.
Andrej Bogdanov (2005). Pseudorandom generators for low degree polynomials. In Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), 21–30.
Andrej Bogdanov & Emanuele Viola (2010). Pseudorandom bits for polynomials. SIAM Journal of Computing 39(6), 2464–2486.
Nader H. Bshouty (2014). Testers and their applications [extended abstract]. In Proc. 5th Annual Innovations in Theoretical Computer Science Conference (ITCS), 327–351.
Lijie Chen, Ce Jin & Richard Ryan Williams (2020). Sharp threshold results for computational complexity. In Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC), 1335-1348.
Lijie Chen & Roei Tell (2019). Bootstrapping results for threshold circuits “just beyond” known lower bounds. In Proc. 51st Annual ACM Symposium on Theory of Computing (STOC), 34–41.
Lijie Chen & Roei Tell (2021). Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. In Proc. 53st Annual ACM Symposium on Theory of Computing (STOC).
Gil Cohen & Amnon Ta-Shma (2013). Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes. Electronic Colloquium on Computational Complexity: ECCC 20, 155.
David A. Cox, John Little & Donal O’Shea (2015). Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, 4th edition.
Dean Doron, Dana Moshkovitz, Justin Oh & David Zuckerman (2020). Nearly optimal pseudorandomness from hardness. In Proc. 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1057–1068.
Zeev Dvir (2009). On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society 22(4), 1093–1097.
Oded Goldreich (2020). Deconstructing 1-local expanders. In Computational complexity and property testing—on the interplay between randomness and computation, volume 12050 of Lecture Notes in Comput. Sci., 220–248. Springer, Cham.
Oded Goldreich & Avi Widgerson (2014). On derandomizing algorithms that err extremely rarely. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC), 109–118. Full version available online at Electronic Colloquium on Computational Complexity: ECCC, 20:152 (Rev. 2), 2013.
Ben Green & Terence Tao (2009). The distribution of polynomials over finite fields, with applications to the Gowers norms. Contributions to Discrete Mathematics 4(2), 1–36.
Venkatesan Guruswami, Atri Rudra1 & Madhu Sudan (2019). Essential Coding Theory. Accessed at https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf.
Venkatesan Guruswami & Madhu Sudan (2001). Extensions to the Johnson Bound. Manuscript.
Elad Haramaty & Amir Shpilka (2010). On the structure of cubic and quartic polynomials. In Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC), 331–340.
Valentine Kabanets & Zhenjian Lu (2018). Satisfiability and derandomization for small polynomial threshold circuits. In Proc. 22nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Art. No. 46, 19.
Tadao Kasami & Nobuki Tokura (1970). On the weight structure of Reed-Muller codes. IEEE Transactions on Information Theory IT-16, 752–759.
Tali Kaufman & Shachar Lovett (2008). Worst Case to Average Case Reductions for Polynomials. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 166–175.
Tali Kaufman, Shachar Lovett & Ely Porat (2012). Weight distribution and list-decoding size of Reed-Muller codes. IEEE Transactions on Information Theory 58(5), 2689–2696.
Adam R. Klivans & Daniel Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), 216–223.
Swastik Kopparty & Sergey Yekhanin (2008). Detecting rational points on hypersurfaces over finite fields. In Proc. 23rd Annual IEEE Conference on Computational Complexity (CCC), 311–320.
Daniel Lewin & Salil Vadhan (1998). Checking polynomial identities over any field: towards a derandomization? In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), 438–447.
Rudolf Lidl & Harald Niederreiter (1997a). Finite fields, volume 20 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2nd edition, xiv+755 . With a foreword by P. M. Cohn.
Rudolf Lidl & Harald Niederreiter (1997b). Finite fields. Number 20. Cambridge university press.
Shachar Lovett (2009). Unconditional pseudorandom generators for low-degree polynomials. Theory of Computing 5, 69–82.
Chi-Jen Lu (2012). Hitting set generators for sparse polynomials over any finite fields. In Proc. 27th Annual IEEE Conference on Computational Complexity (CCC), 280–286.
M. Luby, B. Velickovic & A. Wigderson (1993). Deterministic approximate counting of depth-2 circuits. In Proc. 2nd Israel Symposium on Theory and Computing Systems, 18–24.
F. J. MacWilliams & N. J. A. Sloane (1977). The theory of errorcorrecting codes. II. North-Holland Publishing Co., Amsterdam-New York-Oxford.
R. J. McEliece (1969). Quadratic forms over finite fields and secondorder Reed-Muller codes. Space Program Summary 3(37–58), 28–33.
Joseph Naor & Moni Naor (1993). Small-bias probability spaces: efficient constructions and applications. SIAM Journal of Computing 22(4), 838–856.
Zipei Nie & Anthony Y. Wang (2015). Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry. Journal of Combinatorial Theory. Series A 134, 196–220.
Noam Nisan & David Zuckerman (1996). Randomness is Linear in Space. Journal of Computer and System Sciences 52(1), 43–52.
Rocco A. Servedio & Li-Yang Tan (2018). Luby-Veliˇckovi´c- Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits. In Proc. 22nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), volume 116, Art. No. 56, 20.
Ronen Shaltiel & Christopher Umans (2005). Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM 52(2), 172–216.
Ronen Shaltiel & Emanuele Viola (2022). On Hardness Assumptions Needed for ”Extreme High-End” PRGs and Fast Derandomization. In Proc. 13th Annual Innovations in Theoretical Computer Science Conference (ITCS), 116:1–116:17.
Neil J. A. Sloane & Elwyn R. Berlekamp (1970). Weight enumerator for second-order Reed-Muller codes. IEEE Transactions on Information Theory IT-16, 745–751.
Amnon Ta-Shma & David Zuckerman (2004). Extractor codes. IEEE Transactions on Information Theory 50(12), 3015–3025.
Amnon Ta-Shma, David Zuckerman & Shmuel Safra (2006). Extractors from Reed-Muller codes. Journal of Computer and System Sciences 72(5), 786–812.
Roei Tell (2018). Quantified derandomization of linear threshold circuits. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC), 855–865.
Roei Tell (2019). Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In Computational Complexity.
Roei Tell (2021). How to Find Water in the Ocean: A Survey on Quantified Derandomization. volume 28, 120.
Salil P. Vadhan (2012). Pseudorandomness. Foundations and Trends in Theoretical Computer Science. Now Publishers.
Emanuele Viola (2009a). Guest Column: correlation bounds for polynomials over {0, 1}. SIGACT News 40, 27–44.
Emanuele Viola (2009b). The sum of d small-bias generators fools polynomials of degree d. Computational Complexity 18(2), 209–217.
Emanuele Viola & Avi Wigderson (2017). Local Expanders. Computational Complexity .
Ewald Warning (1935). Bemerkung zur vorstehenden Arbeit von Herrn Chevalley. Abhandlungen aus dem Mathematischen Seminar der Universit¨at Hamburg (11), 76–83.
Andrew C. Yao (1982). Theory and Application of Trapdoor Functions. In Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 80–91.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Doron, D., Ta-Shma, A. & Tell , R. On Hitting-Set Generators for Polynomials that Vanish Rarely. comput. complex. 31, 16 (2022). https://doi.org/10.1007/s00037-022-00229-2
Received:
Published:
DOI: https://doi.org/10.1007/s00037-022-00229-2
Keywords
- Polynomials
- Hitting-Set Generators
- Pseudorandom Generators
- Quantified Derandomization
- Bounded-Degree Closure