Seed-Protecting Extractors

by Gil Cohen, Dean Doron, and Shahar Samocha

Theory of Computing, Volume 21(8), pp. 1-38, 2025

Bibliography with links to cited articles

[1]   Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM, 57(4):20:1–52, 2010. [doi:10.1145/1734213.1734214]

[2]   Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson: 2-source dispersers for no(1) entropy, and Ramsey graphs beating the Frankl–Wilson construction. Ann. Math., 176(3):1483–1543, 2012. [doi:10.4007/annals.2012.176.3.3]

[3]   Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma: Near-optimal erasure list-decodable codes. In Proc. 35th Comput. Complexity Conf. (CCC’20), volume 169, pp. 1:1–27. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.1]

[4]   Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma: An efficient reduction from two-source to nonmalleable extractors: Achieving near-logarithmic min-entropy. SIAM J. Comput., 51(2):31–49, 2022. [doi:10.1137/17M1133245]

[5]   Jean Bourgain: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory, 1(1):1–32, 2005. [doi:10.1142/S1793042105000108]

[6]   Eshan Chattopadhyay, Vipul Goyal, and Xin Li: Non-malleable extractors and codes, with their many tampered extensions. In Proc. 48th STOC, pp. 285–298. ACM Press, 2016. [doi:10.1145/2897518.2897547]

[7]   Eshan Chattopadhyay and Xin Li: Explicit non-malleable extractors, multi-source extractors and almost optimal privacy amplification protocols. In Proc. 57th FOCS, pp. 158–167. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.25]

[8]   Eshan Chattopadhyay and David Zuckerman: Explicit two-source extractors and resilient functions. Ann. Math., 189(3):653–705, 2019. [doi:10.4007/annals.2019.189.3.1]

[9]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. [doi:10.1137/0217015]

[10]   Gil Cohen: Local correlation breakers and applications to three-source extractors and mergers. SIAM J. Comput., 45(4):1297–1338, 2016. [doi:10.1137/15M1029837]

[11]   Gil Cohen: Making the most of advice: new correlation breakers and their applications. In Proc. 57th FOCS, pp. 188–196. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.28]

[12]   Gil Cohen: Non-malleable extractors—New tools and improved constructions. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 8:1–29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.8]

[13]   Gil Cohen: Towards optimal two-source extractors and Ramsey graphs. In Proc. 49th STOC, pp. 1157–1170. ACM Press, 2017. [doi:10.1145/3055399.3055429]

[14]   Gil Cohen: Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. SIAM J. Comput., 50(3):30–67, 2021. Preliminary version in STOC’16. [doi:10.1137/16M1096219]

[15]   Gil Cohen, Ran Raz, and Gil Segev: Nonmalleable extractors with short seeds and applications to privacy amplification. SIAM J. Comput., 43(2):450–476, 2014. Preliminary version in CCC’12. [doi:10.1137/130908634]

[16]   Gil Cohen and Leonard J. Schulman: Extractors for near logarithmic min-entropy. In Proc. 57th FOCS, pp. 178–187. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.27]

[17]   Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman: Privacy amplification and non-malleable extractors via character sums. In Proc. 52nd FOCS, pp. 668–677. IEEE Comp. Soc., 2011. [doi:10.1109/FOCS.2011.67]

[18]   Yevgeniy Dodis and Daniel Wichs: Non-malleable extractors and symmetric key cryptography from weak secrets. In Proc. 41st STOC, pp. 601–610. ACM Press, 2009. [doi:10.1145/1536414.1536496]

[19]   Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan: Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM J. Comput., 42(6):2305–2328, 2013. [doi:10.1137/100783704]

[20]   Oded Goldreich and Avi Wigderson: Robustly self-ordered graphs: Constructions and applications to property testing. TheoretiCS, 1(8788), 2022. Preliminary version in CCC’21. [doi:10.46298/theoretics.22.1]

[21]   Venkatesan Guruswami, Christopher Umans, and Salil Vadhan: Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM, 56(4):20:1–34, 2009. [doi:10.1145/1538902.1538904]

[22]   Xin Li: Three-source extractors for polylogarithmic min-entropy. In Proc. 56th FOCS, pp. 863–882. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.58]

[23]   Xin Li: Improved non-malleable extractors, non-malleable codes and independent source extractors. In Proc. 49th STOC, pp. 1144–1156. ACM Press, 2017. [doi:10.1145/3055399.3055486]

[24]   Xin Li: Non-malleable extractors and non-malleable codes: partially optimal constructions. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 28:1–49. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.28]

[25]   Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson: Extractors: Optimal up to constant factors. In Proc. 35th STOC, pp. 602–611. ACM Press, 2003. [doi:10.1145/780542.780630]

[26]   Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. [doi:10.1006/jcss.1996.0004]

[27]   Jaikumar Radhakrishnan and Amnon Ta-Shma: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discr. Math., 13(1):2–24, 2000. [doi:10.1137/S0895480197329508]

[28]   Ran Raz: Extractors with weak random seeds. In Proc. 37th STOC, pp. 11–20. ACM Press, 2005. [doi:10.1145/1060590.1060593]

[29]   Ronen Shaltiel: An introduction to randomness extractors. In Proc. 38th Internat. Colloq. on Automata, Languages, and Programming (ICALP’11), pp. 21–41. Springer, 2011. [doi:10.1007/978-3-642-22012-8_2]

[30]   Amnon Ta-Shma and Christopher Umans: Better condensers and new extractors from Parvaresh–Vardy codes. In Proc. 27th IEEE Conf. on Comput. Complexity (CCC’12), pp. 309–315. IEEE Comp. Soc., 2012. [doi:10.1109/CCC.2012.25]

[31]   Luca Trevisan: Extractors and pseudorandom generators. J. ACM, 48(4):860–879, 2001. [doi:10.1145/502090.502099]

[32]   Salil P. Vadhan: Pseudorandomness. Found. Trends Theor. Comp. Sci., 7(1–3):1–336, 2012. [doi:10.1561/0400000010]