Document Open Access Logo

On Hitting-Set Generators for Polynomials That Vanish Rarely

Authors Dean Doron, Amnon Ta-Shma, Roei Tell

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.7.pdf
  • Filesize: 0.72 MB
  • 23 pages

Document Identifiers

Author Details

Dean Doron
  • Department of Computer Science, Stanford University, CA, USA
Amnon Ta-Shma
  • The Blavatnik School of Computer Science, Tel-Aviv University, Israel
Roei Tell
  • Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel

Funding

  • Doron, Dean: Supported by a Motwani Postdoctoral Fellowship and by NSF award CCF-1763311.
  • Ta-Shma, Amnon: Supported by ISF grant 18/952 and by Len Blavatnik and the Blavatnik Family foundation.
  • Tell, Roei: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702).

Acknowledgements

We are grateful to an exceptionally helpful anonymous reviewer, who pointed us to the work of Nie and Wang [Nie and Wang, 2015] and to follow-up works, suggested an alternative proof strategy for the lower bound in the special case of prime fields (the alternative proof for this special case appears in the full version), and helped improve our initial results.

Cite As Get BibTex

Dean Doron, Amnon Ta-Shma, and Roei Tell. On Hitting-Set Generators for Polynomials That Vanish Rarely. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.7

Abstract

The problem of constructing hitting-set 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 a hitting-set generator for polynomials p: 𝔽ⁿ → 𝔽 of degree d if we are guaranteed that the polynomial vanishes on at most an ε > 0 fraction of its inputs? We will specifically be interested in tiny values of ε≪ d/|𝔽|. 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:  
- Over fields of size 2 ≤ |𝔽| ≤ poly(n), we show that the seed length of any hitting-set generator for polynomials of degree d ≤ n^{.49} that vanish on at most ε = |𝔽|^{-t} of their inputs is at least Ω((d/t)⋅log(n)). 
- Over 𝔽₂, we show that there exists a (non-explicit) hitting-set generator for polynomials of degree d ≤ n^{.99} that vanish on at most ε = |𝔽|^{-t} of their inputs with seed length O((d-t)⋅log(n)). We also show a polynomial-time computable hitting-set generator with seed length O((d-t)⋅(2^{d-t}+log(n))). 
In addition, we prove that the problem we study is closely related to the following question: "Does there exist a small set S ⊆ 𝔽ⁿ 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Hitting-set generators
  • Polynomials over finite fields
  • Quantified derandomization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Emmanuel Abbe, Amir Shpilka, and Avi Wigderson. Reed-Muller codes for random erasures and errors. IEEE Transactions on Information Theory, 61(10):5229-5252, 2015. Google Scholar
  2. N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38(2):509-516, 1992. Google Scholar
  3. Peter Beelen and Mrinmoy Datta. Generalized Hamming weights of affine Cartesian codes. Finite Fields and their Applications, 51:130-145, 2018. Google Scholar
  4. E. R. Berlekamp and N. J. A. Sloane. Restrictions on weight distribution of Reed-Muller codes. Information and Control, 14:442-456, 1969. Google Scholar
  5. Arnab Bhattacharyya. Polynomial decompositions in polynomial time. In Proc. 22nd European Symposia on Algorithms, pages 125-136. Springer, 2014. Google Scholar
  6. Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta. On higher-order Fourier analysis over non-prime fields. In Proc. 20th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages Art. No. 23, 29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.23.
  7. Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani. Algorithmic regularity for polynomials and applications. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1870-1889, 2015. Google Scholar
  8. Markus Bläser, Moritz Hardt, and David Steurer. 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), pages 345-356, 2008. Google Scholar
  9. Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In Proc. 37th Annual ACM Symposium on Theory of Computing (STOC), pages 21-30. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060594.
  10. Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM Journal of Computing, 39(6):2464-2486, 2010. Google Scholar
  11. Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits "just beyond" known lower bounds. In Proc. 51st Annual ACM Symposium on Theory of Computing (STOC), pages 34-41, 2019. Google Scholar
  12. Gil Cohen and Amnon Ta-Shma. Pseudorandom generators for low degree polynomials from algebraic geometry codes. Electronic Colloquium on Computational Complexity: ECCC, 20:155, 2013. Google Scholar
  13. David A. Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. Google Scholar
  14. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. Electronic Colloquium on Computational Complexity: ECCC, 26:99, 2019. Google Scholar
  15. Dean Doron, Amnon Ta-Shma, and Roei Tell. On hitting-set generators for polynomials that vanish rarely (rev. 1). Electronic Colloquium on Computational Complexity: ECCC, 26:119, 2019. Google Scholar
  16. Zeev Dvir. On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society, 22(4):1093-1097, 2009. Google Scholar
  17. Oded Goldreich. Deconstructing 1-local expanders. Electronic Colloquium on Computational Complexity: ECCC, 23:152, 2016. Google Scholar
  18. Oded Goldreich and Avi Widgerson. On derandomizing algorithms that err extremely rarely. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC), pages 109-118. ACM, 2014. Full version available online at Electronic Colloquium on Computational Complexity: ECCC, 20:152 (Rev. 2), 2013. URL: https://doi.org/10.1145/2591796.2591808.
  19. Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. Contributions to Discrete Mathematics, 4(2):1-36, 2009. Google Scholar
  20. Venkatesan Guruswami, Atri Rudra1, and Madhu Sudan. Essential coding theory, 2019. Accessed at URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf.
  21. Elad Haramaty and Amir Shpilka. On the structure of cubic and quartic polynomials. In Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 331-340. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806736.
  22. Tadao Kasami and Nobuki Tokura. On the weight structure of Reed-Muller codes. IEEE Transactions on Information Theory, IT-16:752-759, 1970. Google Scholar
  23. Tali Kaufman and Shachar Lovett. Worst case to average case reductions for polynomials. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 166-175, 2008. Google Scholar
  24. Tali Kaufman, Shachar Lovett, and Ely Porat. Weight distribution and list-decoding size of Reed-Muller codes. IEEE Transactions on Information Theory, 58(5):2689-2696, 2012. Google Scholar
  25. Adam R. Klivans and Daniel Spielman. Randomness efficient identity testing of multivariate polynomials. In Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 216-223, 2001. Google Scholar
  26. Daniel Lewin and Salil Vadhan. Checking polynomial identities over any field: towards a derandomization? In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), pages 438-447. ACM, 1998. URL: https://doi.org/10.1145/276698.276856.
  27. Shachar Lovett. Unconditional pseudorandom generators for low-degree polynomials. Theory of Computing, 5:69-82, 2009. Google Scholar
  28. Chi-Jen Lu. Hitting set generators for sparse polynomials over any finite fields. In Proc. 27th Annual IEEE Conference on Computational Complexity (CCC), pages 280-286. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/CCC.2012.20.
  29. M. Luby, B. Velickovic, and A. Wigderson. Deterministic approximate counting of depth-2 circuits. In Proc. 2nd Israel Symposium on Theory and Computing Systems, pages 18-24, 1993. Google Scholar
  30. F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. II. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Google Scholar
  31. R. J. McEliece. Quadratic forms over finite fields and second-order Reed-Muller codes. Space Program Summary, 3(37-58):28-33, 1969. Google Scholar
  32. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM Journal of Computing, 22(4):838-856, 1993. Google Scholar
  33. Zipei Nie and Anthony Y. Wang. Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry. Journal of Combinatorial Theory. Series A, 134:196-220, 2015. Google Scholar
  34. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  35. Rocco A. Servedio and Li-Yang Tan. Luby-Veličković-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, pages Art. No. 56, 20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.56.
  36. Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM, 52(2):172-216, 2005. Google Scholar
  37. Neil J. A. Sloane and Elwyn R. Berlekamp. Weight enumerator for second-order Reed-Muller codes. IEEE Transactions on Information Theory, IT-16:745-751, 1970. Google Scholar
  38. Amnon Ta-Shma and David Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50(12):3015-3025, 2004. Google Scholar
  39. Amnon Ta-Shma, David Zuckerman, and Shmuel Safra. Extractors from Reed-Muller codes. Journal of Computer and System Sciences,, 72(5):786-812, 2006. Google Scholar
  40. Roei Tell. Improved bounds for quantified derandomization of constant-depth circuits and polynomials. In Computational Complexity, 2019. Google Scholar
  41. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science. Now Publishers, 2012. Google Scholar
  42. Emanuele Viola. Guest column: correlation bounds for polynomials over 0,1. SIGACT News, 40:27-44, February 2009. Google Scholar
  43. Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. Computational Complexity, 18(2):209-217, 2009. Google Scholar
  44. Emanuele Viola and Avi Wigderson. Local expanders. Computational Complexity, 2017. Google Scholar
  45. Ewald Warning. Bemerkung zur vorstehenden arbeit von herrn chevalley. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 1935. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact