Low-Degree Polynomials Extract From Local Sources

Authors Omar Alrabiah , Eshan Chattopadhyay , Jesse Goodman , Xin Li , João Ribeiro



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.10.pdf
  • Filesize: 0.85 MB
  • 20 pages

Document Identifiers

Author Details

Omar Alrabiah
  • EECS Department, University of California, Berkeley, CA, USA
Eshan Chattopadhyay
  • Computer Science Department, Cornell University, Ithaca, NY, USA
Jesse Goodman
  • Computer Science Department, Cornell University, Ithaca, NY, USA
Xin Li
  • Computer Science Department, Johns Hopkins University, Baltimore, MD, USA
João Ribeiro
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Cite AsGet BibTex

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.10

Abstract

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Randomness extractors
  • local sources
  • samplable sources
  • AC⁰ circuits
  • branching programs
  • low-degree polynomials
  • Chevalley-Warning

Metrics

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

References

  1. Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low-degree polynomials are hard to approximate. Comput. Complex., 21(1):63-81, 2012. URL: https://doi.org/10.1007/s00037-011-0020-6.
  2. Andrej Bogdanov and Siyao Guo. Sparse extractor families for all the entropy. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 553-560. Association for Computing Machinery, 2013. URL: https://doi.org/10.1145/2422436.2422496.
  3. Eshan Chattopadhyay and Jesse Goodman. Improved extractors for small-space sources. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 610-621, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00066.
  4. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li. Extractors for adversarial sources via extremal hypergraphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1184-1197, 2020. Google Scholar
  5. Kuan Cheng and Xin Li. Randomness extraction in AC⁰ and with small locality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), pages 37:1-37:20, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.37.
  6. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. URL: https://doi.org/10.1137/0217015.
  7. Gil Cohen and Avishay Tal. Two structural results for low degree polynomials and applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), pages 680-709, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.680.
  8. Ernie Croot, Vsevolod F Lev, and Péter Pál Pach. Progression-free sets in are exponentially small. Annals of Mathematics, pages 331-337, 2017. Google Scholar
  9. Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. ACM Trans. Comput. Theory, 4(1), March 2012. URL: https://doi.org/10.1145/2141938.2141941.
  10. Yevgeniy Dodis and Kevin Yeo. Doubly-affine extractors, and their applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021), pages 13:1-13:23, 2021. URL: https://doi.org/10.4230/LIPIcs.ITC.2021.13.
  11. Oded Goldreich, Emanuele Viola, and Avi Wigderson. On randomness extraction in AC⁰. In 30th Conference on Computational Complexity (CCC 2015), pages 601-668, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.601.
  12. Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine extractors and AC⁰-parity. Electron. Colloquium Comput. Complex., page 137, 2021. URL: https://eccc.weizmann.ac.il/report/2021/137.
  13. Jesse Kamp, Anup Rao, Salil Vadhan, and David Zuckerman. Deterministic extractors for small-space sources. J. Comput. Syst. Sci., 77(1):191-220, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.014.
  14. 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. URL: https://doi.org/10.1109/TIT.2012.2184841.
  15. Jiatu Li and Tianqi Yang. 3.1n-o(n) circuit lower bounds for explicit functions. In Electron. Colloquium Comput. Complex., volume 28, page 23, 2021. Google Scholar
  16. Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 168-177, 2016. URL: https://doi.org/10.1109/FOCS.2016.26.
  17. Chi-Jen Lu. Encryption against storage-bounded adversaries from on-line strong extractors. J. Cryptol., 17(1):27-42, 2004. URL: https://doi.org/10.1007/s00145-003-0217-1.
  18. Luca Trevisan and Salil Vadhan. Extracting randomness from samplable distributions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 32-42, 2000. URL: https://doi.org/10.1109/SFCS.2000.892063.
  19. Salil P. Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Cryptol., 17(1):43-77, 2004. URL: https://doi.org/10.1007/s00145-003-0237-x.
  20. Emanuele Viola. The complexity of constructing pseudorandom generators from hard functions. Comput. Complex., 13(3-4):147-188, 2005. URL: https://doi.org/10.1007/s00037-004-0187-1.
  21. Emanuele Viola. Extractors for circuit sources. SIAM Journal on Computing, 43(2):655-672, 2014. URL: https://doi.org/10.1137/11085983X.
  22. Emanuele Viola. Quadratic maps are hard to sample. ACM Trans. Comput. Theory, 8(4), June 2016. URL: https://doi.org/10.1145/2934308.
  23. Emanuele Viola. Sampling lower bounds: Boolean average-case and permutations. SIAM Journal on Computing, 49(1):119-137, 2020. URL: https://doi.org/10.1137/18M1198405.
  24. Ewald Warning. Bemerkung zur vorstehenden arbeit von Herrn Chevalley. Abh. Math. Sem. Univ. Hamburg, 11:76-83, 1936. 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