Explicit two-source extractors and resilient functions

Abstract

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$ for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\mathrm{polylog}(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 – \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. and matching an independent work by Cohen.

  • [AL93] Go to document M. Ajtai and N. Linial, "The influence of large coalitions," Combinatorica, vol. 13, iss. 2, pp. 129-145, 1993.
    @ARTICLE{AL93,
      author = {Ajtai, Miklós and Linial, Nathal},
      title = {The influence of large coalitions},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {13},
      year = {1993},
      number = {2},
      pages = {129--145},
      issn = {0209-9683},
      mrclass = {05A99 (06E30)},
      mrnumber = {1237037},
      doi = {10.1007/BF01303199},
      url = {https://doi.org/10.1007/BF01303199},
      zblnumber = {0807.90148},
      }
  • [Alon98] Go to document N. Alon, "The Shannon capacity of a union," Combinatorica, vol. 18, iss. 3, pp. 301-310, 1998.
    @ARTICLE{Alon98,
      author = {Alon, Noga},
      title = {The {S}hannon capacity of a union},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {18},
      year = {1998},
      number = {3},
      pages = {301--310},
      issn = {0209-9683},
      mrclass = {05C35 (94A40)},
      mrnumber = {1721946},
      doi = {10.1007/PL00009824},
      url = {https://doi.org/10.1007/PL00009824},
      zblnumber = {0921.05039},
      }
  • [AGM03] Go to document N. Alon, O. Goldreich, and Y. Mansour, "Almost $k$-wise independence versus $k$-wise independence," Inform. Process. Lett., vol. 88, iss. 3, pp. 107-110, 2003.
    @ARTICLE{AGM03,
      author = {Alon, Noga and Goldreich, Oded and Mansour, Yishay},
      title = {Almost {$k$}-wise independence versus {$k$}-wise independence},
      journal = {Inform. Process. Lett.},
      fjournal = {Information Processing Letters},
      volume = {88},
      year = {2003},
      number = {3},
      pages = {107--110},
      issn = {0020-0190},
      mrclass = {68W20 (60C05 68W40)},
      mrnumber = {2006353},
      doi = {10.1016/S0020-0190(03)00359-4},
      url = {https://doi.org/10.1016/S0020-0190(03)00359-4},
      zblnumber = {1178.68251},
      }
  • [AS92] N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley & Sons, Inc., New York, 1992.
    @BOOK{AS92,
      author = {Alon, Noga and Spencer, Joel H.},
      title = {The Probabilistic Method},
      series = {Wiley-Interscience Series in Discrete Mathematics and Optimization},
      note = {With an appendix by Paul Erdős, A Wiley-Interscience Publication},
      publisher = {John Wiley \& Sons, Inc., New York},
      year = {1992},
      pages = {xvi+254},
      isbn = {0-471-53588-5},
      mrclass = {60-02 (05C80 11K99 60C05)},
      mrnumber = {1140703},
      mrreviewer = {Bert Fristedt},
      zblnumber = {0767.05001},
      }
  • [arora2009computational] Go to document S. Arora and B. Barak, Computational Complexity. A Modern Approach, Cambridge University Press, Cambridge, 2009.
    @BOOK{arora2009computational,
      author = {Arora, Sanjeev and Barak, Boaz},
      title = {Computational Complexity. A Modern Approach},
      publisher = {Cambridge University Press, Cambridge},
      year = {2009},
      pages = {xxiv+579},
      isbn = {978-0-521-42426-4},
      mrclass = {68-01 (03D15 68Q15 68Q17 68Q25 81P68 94A60)},
      mrnumber = {2500087},
      mrreviewer = {Ulrich Tamm},
      doi = {10.1017/CBO9780511804090},
      url = {https://doi.org/10.1017/CBO9780511804090},
      zblnumber = {1193.68112},
      }
  • [Barak04] B. Barak, A Simple Explicit Construction of an $n^{\tilde{O}(\log n)}$-Ramsey graph, 2006.
    @MISC{Barak04,
      author = {Barak, Boaz},
      title = {A Simple Explicit Construction of an $n^{\tilde{O}(\log n)}$-{R}amsey graph},
      year = {2006},
      zblnumber = {},
      arxiv = {math/0601651},
      }
  • [BarH] Go to document B. Barak and S. Halevi, "A model and architecture for pseudo-random generation with applications to /dev/random," in Proceedings of the 12th ACM Conference on Computer and Communications Security, , 2005, pp. 203-212.
    @INCOLLECTION{BarH,
      author = {Barak, Boaz and Halevi, S.},
      title = {A model and architecture for pseudo-random generation with applications to /dev/random},
      booktitle = {Proceedings of the 12th {ACM} {C}onference on {C}omputer and {C}ommunications {S}ecurity},
      year = {2005},
      pages = {203--212},
      zblnumber = {},
      doi = {10.1145/1102120.1102148},
      }
  • [BIW] Go to document B. Barak, R. Impagliazzo, and A. Wigderson, "Extracting randomness using few independent sources," SIAM J. Comput., vol. 36, iss. 4, pp. 1095-1118, 2006.
    @ARTICLE{BIW,
      author = {Barak, Boaz and Impagliazzo, Russell and Wigderson, Avi},
      title = {Extracting randomness using few independent sources},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {36},
      year = {2006},
      number = {4},
      pages = {1095--1118},
      issn = {0097-5397},
      mrclass = {68Q10 (05C55 68W20)},
      mrnumber = {2272272},
      mrreviewer = {Heng Liang},
      doi = {10.1137/S0097539705447141},
      url = {https://doi.org/10.1137/S0097539705447141},
      zblnumber = {1127.68030},
      }
  • [BKSSW10] Go to document B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson, "Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors," J. ACM, vol. 57, iss. 4, p. 20, 2010.
    @ARTICLE{BKSSW10,
      author = {Barak, Boaz and Kindler, G. and Shaltiel, R. and Sudakov, B. and Wigderson, A.},
      title = {Simulating independence: new constructions of condensers, {R}amsey graphs, dispersers, and extractors},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {57},
      year = {2010},
      number = {4},
      pages = {Art. 20, 52},
      issn = {0004-5411},
      mrclass = {05C85 (05C55 05D40 68Q87 68R10 68W20)},
      mrnumber = {2677118},
      doi = {10.1145/1734213.1734214},
      url = {https://doi.org/10.1145/1734213.1734214},
      zblnumber = {1327.68172},
      }
  • [BRSW12] Go to document B. Barak, A. Rao, R. Shaltiel, and A. Wigderson, "2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction," Ann. of Math. (2), vol. 176, iss. 3, pp. 1483-1543, 2012.
    @ARTICLE{BRSW12,
      author = {Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi},
      title = {2-source dispersers for {$n^{o(1)}$} entropy, and {R}amsey graphs beating the {F}rankl-{W}ilson construction},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {176},
      year = {2012},
      number = {3},
      pages = {1483--1543},
      issn = {0003-486X},
      mrclass = {05C55 (68Q87)},
      mrnumber = {2979856},
      doi = {10.4007/annals.2012.176.3.3},
      url = {https://doi.org/10.4007/annals.2012.176.3.3},
      zblnumber = {1256.05146},
      }
  • [BACDT18] Go to document A. Ben-Aroya, G. Cohen, D. Doron, and A. Ta-Shma, "Two-source condensers with low error and small entropy gap via entropy-resilient functions," Electronic Colloq. Computational Complexity (ECCC), vol. 25, p. 66, 2018.
    @ARTICLE{BACDT18,
      author = {Ben{-}Aroya, A. and Cohen, G. and Doron, D. and Ta{-}Shma, A.},
      title = {Two-source condensers with low error and small entropy gap via entropy-resilient functions},
      journal = {Electronic Colloq. Computational Complexity {(ECCC)}},
      volume = {25},
      year = {2018},
      pages = {66},
      zblnumber = {},
      url = {file:///Users/annals/Downloads/TR18-066%20(8).pdf},
      }
  • [BADT17] Go to document A. Ben-Aroya, D. Doron, and A. Ta-Shma, "An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy," in STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 1185-1194.
    @INCOLLECTION{BADT17,
      author = {Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon},
      title = {An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy},
      booktitle = {S{TOC}'17---{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {1185--1194},
      publisher = {ACM, New York},
      year = {2017},
      mrclass = {05D10},
      mrnumber = {3678261},
      zblnumber = {1370.68082},
      doi = {10.1145/3055399.3055423},
      }
  • [BADT18] Go to document A. Ben-Aroya, D. Doron, and A. Ta-Shma, "Near-optimal strong dispersers, erasure list-decodable codes and friends," Electron. Colloq. Computational Complexity (ECCC), vol. 25, p. 65, 2018.
    @ARTICLE{BADT18,
      author = {Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon},
      title = {Near-optimal strong dispersers, erasure list-decodable codes and friends},
      journal = {Electron. Colloq. Computational Complexity {(ECCC)}},
      volume = {25},
      year = {2018},
      pages = {65},
      url = {https://eccc.weizmann.ac.il/report/2018/065},
      zblnumber = {},
      }
  • [BOL85] Go to document A. Ben-Aroya and N. Linial, "Collective coin flipping, robust voting schemes and minima of Banzhaf values," in 26th Annual Symposium on Foundations of Computer Science, , 1985, pp. 408-416.
    @INCOLLECTION{BOL85,
      author = {Ben-Aroya, Avraham and Linial, N.},
      title = {Collective coin flipping, robust voting schemes and minima of {B}anzhaf values},
      booktitle = {26th Annual Symposium on Foundations of Computer Science},
      venue = {Portland, Oregon, USA, 21-23 October 1985},
      year = {1985},
      pages = {408--416},
      doi = {10.1109/SFCS.1985.15},
      zblnumber = {},
      }
  • [BS89] Go to document R. Boppona and J. Spencer, "A useful elementary correlation inequality," J. Combin. Theory Ser. A, vol. 50, iss. 2, pp. 305-307, 1989.
    @ARTICLE{BS89,
      author = {Boppona, Ravi and Spencer, Joel},
      title = {A useful elementary correlation inequality},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {50},
      year = {1989},
      number = {2},
      pages = {305--307},
      issn = {0097-3165},
      mrclass = {60C05},
      mrnumber = {0989201},
      mrreviewer = {Zbigniew Palka},
      doi = {10.1016/0097-3165(89)90022-8},
      url = {https://doi.org/10.1016/0097-3165(89)90022-8},
      zblnumber = {0663.60007},
      }
  • [B2] Go to document J. Bourgain, "More on the sum-product phenomenon in prime fields and its applications," Int. J. Number Theory, vol. 1, iss. 1, pp. 1-32, 2005.
    @ARTICLE{B2,
      author = {Bourgain, J.},
      title = {More on the sum-product phenomenon in prime fields and its applications},
      journal = {Int. J. Number Theory},
      fjournal = {International Journal of Number Theory},
      volume = {1},
      year = {2005},
      number = {1},
      pages = {1--32},
      issn = {1793-0421},
      mrclass = {11B75 (11L05)},
      mrnumber = {2172328},
      mrreviewer = {Sergeĭ V. Konyagin},
      doi = {10.1142/S1793042105000108},
      url = {https://doi.org/10.1142/S1793042105000108},
      zblnumber = {1173.11310},
      }
  • [Bra07] Go to document M. Braverman, "Polylogarithmic independence fools ${ AC}^0$ circuits," J. ACM, vol. 57, iss. 5, p. 28, 2010.
    @ARTICLE{Bra07,
      author = {Braverman, Mark},
      title = {Polylogarithmic independence fools {${\rm AC}^0$} circuits},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {57},
      year = {2010},
      number = {5},
      pages = {Art. 28, 10},
      issn = {0004-5411},
      mrclass = {68Q15 (60E99)},
      mrnumber = {2683586},
      doi = {10.1145/1754399.1754401},
      url = {https://doi.org/10.1145/1754399.1754401},
      zblnumber = {1327.68108},
      }
  • [CGL15] Go to document E. Chattopadhyay, V. Goyal, and X. Li, "Non-malleable extractors and codes, with their many tampered extensions," in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 285-298.
    @INCOLLECTION{CGL15,
      author = {Chattopadhyay, Eshan and Goyal, Vipul and Li, Xin},
      title = {Non-malleable extractors and codes, with their many tampered extensions},
      booktitle = {S{TOC}'16---{P}roceedings of the 48th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {285--298},
      publisher = {ACM, New York},
      year = {2016},
      mrclass = {94B05},
      mrnumber = {3536573},
      zblnumber = {1377.94042},
      doi = {10.1145/2897518.2897547},
      }
  • [CL16nm] Go to document E. Chattopadhyay and X. Li, "Explicit non-malleable extractors, multi-source extractors and almost optimal privacy amplification protocols," in 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 158-167.
    @INCOLLECTION{CL16nm,
      author = {Chattopadhyay, Eshan and Li, Xin},
      title = {Explicit non-malleable extractors, multi-source extractors and almost optimal privacy amplification protocols},
      booktitle = {57th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2016},
      pages = {158--167},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2016},
      mrclass = {68Q87},
      mrnumber = {3630976},
      zblnumber = {},
      doi = {10.1109/FOCS.2016.25},
      }
  • [CL15] E. Chattopadhyay and X. Li, "Extractors for sumset sources," in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 299-311.
    @INCOLLECTION{CL15,
      author = {Chattopadhyay, Eshan and Li, Xin},
      title = {Extractors for sumset sources},
      booktitle = {S{TOC}'16---{P}roceedings of the 48th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {299--311},
      publisher = {ACM, New York},
      year = {2016},
      mrclass = {68R05 (60E15 62B10 68W20)},
      mrnumber = {3536574},
      zblnumber = {1377.94014},
      }
  • [CG88] Go to document B. Chor and O. Goldreich, "Unbiased bits from sources of weak randomness and probabilistic communication complexity," SIAM J. Comput., vol. 17, iss. 2, pp. 230-261, 1988.
    @ARTICLE{CG88,
      author = {Chor, Benny and Goldreich, Oded},
      title = {Unbiased bits from sources of weak randomness and probabilistic communication complexity},
      note = {Special issue on cryptography},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {17},
      year = {1988},
      number = {2},
      pages = {230--261},
      issn = {0097-5397},
      mrclass = {68Q25},
      mrnumber = {0935339},
      mrreviewer = {Claus-Peter Schnorr},
      doi = {10.1137/0217015},
      url = {https://doi.org/10.1137/0217015},
      zblnumber = {0644.94008},
      }
  • [C15] Go to document G. Cohen, "Local correlation breakers and applications to three-source extractors and mergers," in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 845-862.
    @INCOLLECTION{C15,
      author = {Cohen, Gil},
      title = {Local correlation breakers and applications to three-source extractors and mergers},
      booktitle = {2015 {IEEE} 56th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2015},
      pages = {845--862},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2015},
      mrclass = {62B10 (68Q87)},
      mrnumber = {3473344},
      zblnumber = {},
      doi = {10.1109/FOCS.2015.57},
      }
  • [Cohen16_Adv] Go to document G. Cohen, "Making the most of advice: new correlation breakers and their applications," in 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 188-196.
    @INCOLLECTION{Cohen16_Adv,
      author = {Cohen, Gil},
      title = {Making the most of advice: new correlation breakers and their applications},
      booktitle = {57th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2016},
      pages = {188--196},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2016},
      mrclass = {68Q87},
      mrnumber = {3630979},
      zblnumber = {},
      doi = {10.1109/FOCS.2016.28},
      }
  • [Coh15b] Go to document G. Cohen, "Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs," in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 278-284.
    @INCOLLECTION{Coh15b,
      author = {Cohen, Gil},
      title = {Two-source dispersers for polylogarithmic entropy and improved {R}amsey graphs},
      booktitle = {S{TOC}'16---{P}roceedings of the 48th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {278--284},
      publisher = {ACM, New York},
      year = {2016},
      mrclass = {05C55},
      mrnumber = {3536572},
      zblnumber = {1376.05086},
      doi = {10.1145/2897518.2897530},
      }
  • [Cohen17] Go to document G. Cohen, "Towards optimal two-source extractors and Ramsey graphs," in STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 1157-1170.
    @INCOLLECTION{Cohen17,
      author = {Cohen, Gil},
      title = {Towards optimal two-source extractors and {R}amsey graphs},
      booktitle = {S{TOC}'17---{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {1157--1170},
      publisher = {ACM, New York},
      year = {2017},
      mrclass = {05D10 (68R10)},
      mrnumber = {3678259},
      zblnumber = {1370.68084},
      doi = {10.1145/3055399.3055429},
      }
  • [CRS11] Go to document G. Cohen, R. Raz, and G. Segev, "Nonmalleable extractors with short seeds and applications to privacy amplification," SIAM J. Comput., vol. 43, iss. 2, pp. 450-476, 2014.
    @ARTICLE{CRS11,
      author = {Cohen, Gil and Raz, Ran and Segev, Gil},
      title = {Nonmalleable extractors with short seeds and applications to privacy amplification},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {43},
      year = {2014},
      number = {2},
      pages = {450--476},
      issn = {0097-5397},
      mrclass = {68Q99 (68M12 68R05)},
      mrnumber = {3180869},
      doi = {10.1137/130908634},
      url = {https://doi.org/10.1137/130908634},
      zblnumber = {1302.94040},
      }
  • [DodO] Go to document Y. Dodis and R. Oliveira, "On extracting private randomness over a public channel," in Approximation, Randomization, and Combinatorial Optimization, Springer, Berlin, 2003, vol. 2764, pp. 252-263.
    @INCOLLECTION{DodO,
      author = {Dodis, Yevgeniy and Oliveira, Roberto},
      title = {On extracting private randomness over a public channel},
      booktitle = {Approximation, Randomization, and Combinatorial Optimization},
      series = {Lecture Notes in Comput. Sci.},
      volume = {2764},
      pages = {252--263},
      publisher = {Springer, Berlin},
      year = {2003},
      mrclass = {68W20 (68P30 94A60 94A62)},
      mrnumber = {2080797},
      doi = {10.1007/978-3-540-45198-3_22},
      url = {https://doi.org/10.1007/978-3-540-45198-3_22},
      zblnumber = {1279.68350},
      }
  • [DLWZ11] Go to document Y. Dodis, X. Li, T. D. Wooley, and D. Zuckerman, "Privacy amplification and nonmalleable extractors via character sums," SIAM J. Comput., vol. 43, iss. 2, pp. 800-830, 2014.
    @ARTICLE{DLWZ11,
      author = {Dodis, Yevgeniy and Li, Xin and Wooley, Trevor D. and Zuckerman, David},
      title = {Privacy amplification and nonmalleable extractors via character sums},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {43},
      year = {2014},
      number = {2},
      pages = {800--830},
      issn = {0097-5397},
      mrclass = {94A60 (68Q10 68W20)},
      mrnumber = {3504683},
      mrreviewer = {M. I. Dekhtyar},
      doi = {10.1137/120868414},
      url = {https://doi.org/10.1137/120868414},
      zblnumber = {1302.94043},
      }
  • [DW09] Go to document Y. Dodis and D. Wichs, "Non-malleable extractors and symmetric key cryptography from weak secrets," in STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, New York, 2009, pp. 601-610.
    @INCOLLECTION{DW09,
      author = {Dodis, Yevgeniy and Wichs, Daniel},
      title = {Non-malleable extractors and symmetric key cryptography from weak secrets},
      booktitle = {S{TOC}'09---{P}roceedings of the 2009 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing},
      pages = {601--610},
      publisher = {ACM, New York},
      year = {2009},
      mrclass = {94A62 (68M12)},
      mrnumber = {2780106},
      zblnumber = {1304.94048},
      doi = {10.1145/1536414.1536496},
      }
  • [DKSS09] Go to document Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan, "Extensions to the method of multiplicities, with applications to Kakeya sets and mergers," in 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 181-190.
    @INCOLLECTION{DKSS09,
      author = {Dvir, Zeev and Kopparty, Swastik and Saraf, Shubhangi and Sudan, Madhu},
      title = {Extensions to the method of multiplicities, with applications to {K}akeya sets and mergers},
      booktitle = {2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2009},
      pages = {181--190},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2009},
      mrclass = {68R05 (68Q87)},
      mrnumber = {2648400},
      doi = {10.1109/FOCS.2009.40},
      url = {https://doi.org/10.1109/FOCS.2009.40},
      zblnumber = {1292.68119},
      }
  • [E47] Go to document P. ErdHos, "Some remarks on the theory of graphs," Bull. Amer. Math. Soc., vol. 53, iss. 4, pp. 292-294, 1947.
    @ARTICLE{E47,
      author = {Erd{ő}s, P.},
      title = {Some remarks on the theory of graphs},
      journal = {Bull. Amer. Math. Soc.},
      volume = {53},
      number = {4},
      year = {1947},
      pages = {292--294},
      url = {http://projecteuclid.org/euclid.bams/1183510596},
      zblnumber = {0032.19203},
      mrnumber = {0019911},
      doi= {10.1090/S0002-9904-1947-08785-1},
      }
  • [F99] Go to document U. Feige, "Noncryptographic selection protocols," in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, , 1999, pp. 142-153.
    @INCOLLECTION{F99,
      author = {Feige, U.},
      title = {Noncryptographic selection protocols},
      booktitle = {Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science},
      year = {1999},
      pages = {142--153},
      zblnumber = {},
      doi = {10.1109/SFFCS.1999.814586},
      }
  • [FW81] Go to document P. Frankl and R. M. Wilson, "Intersection theorems with geometric consequences," Combinatorica, vol. 1, iss. 4, pp. 357-368, 1981.
    @ARTICLE{FW81,
      author = {Frankl, P. and Wilson, R. M.},
      title = {Intersection theorems with geometric consequences},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {1},
      year = {1981},
      number = {4},
      pages = {357--368},
      issn = {0209-9683},
      mrclass = {05C35 (05A17 05A20 05C15)},
      mrnumber = {0647986},
      mrreviewer = {E. C. Milner},
      doi = {10.1007/BF02579457},
      url = {https://doi.org/10.1007/BF02579457},
      zblnumber = {0498.05048},
      }
  • [GRS06] Go to document A. Gabizon, R. Raz, and R. Shaltiel, "Deterministic extractors for bit-fixing sources by obtaining an independent seed," SIAM J. Comput., vol. 36, iss. 4, pp. 1072-1094, 2006.
    @ARTICLE{GRS06,
      author = {Gabizon, Ariel and Raz, Ran and Shaltiel, Ronen},
      title = {Deterministic extractors for bit-fixing sources by obtaining an independent seed},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {36},
      year = {2006},
      number = {4},
      pages = {1072--1094},
      issn = {0097-5397},
      mrclass = {68R05 (68Q99)},
      mrnumber = {2272271},
      mrreviewer = {Gheorghe Barbu},
      doi = {10.1137/S0097539705447049},
      url = {https://doi.org/10.1137/S0097539705447049},
      zblnumber = {1118.68096},
      }
  • [gsv] Go to document S. Goldwasser, M. Sudan, and V. Vaikuntanathan, "Distributed computing with imperfect randomness," in Proceedings of the 19th International Symposium on Distributed Computing DISC 2005, Springer-Verlag, New York, 2005, vol. 3724, pp. 288-302.
    @INCOLLECTION{gsv,
      author = {Goldwasser, S. and Sudan, M. and Vaikuntanathan, V.},
      title = {Distributed computing with imperfect randomness},
      booktitle = {Proceedings of the 19th International Symposium on Distributed Computing {DISC} 2005},
      note = {(P. Fraigniaud, ed.)},
      series = {Lect. Notes Comput. Sci.},
      volume = {3724},
      publisher = {Springer-Verlag, New York},
      year = {2005},
      pages = {288--302},
      zblnumber = {1171.68860},
      doi = {10.1007/11561927_22},
      }
  • [Gopalan14] Go to document P. Gopalan, "Constructing Ramsey graphs from Boolean function representations," Combinatorica, vol. 34, iss. 2, pp. 173-206, 2014.
    @ARTICLE{Gopalan14,
      author = {Gopalan, Parikshit},
      title = {Constructing {R}amsey graphs from {B}oolean function representations},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {34},
      year = {2014},
      number = {2},
      pages = {173--206},
      issn = {0209-9683},
      mrclass = {05C69 (05C55 06E30)},
      mrnumber = {3213847},
      doi = {10.1007/s00493-014-2367-1},
      url = {https://doi.org/10.1007/s00493-014-2367-1},
      zblnumber = {1349.05230},
      }
  • [Grolmusz00] Go to document V. Grolmusz, "Low rank co-diagonal matrices and Ramsey graphs," Electron. J. Combin., vol. 7, p. 15, 2000.
    @ARTICLE{Grolmusz00,
      author = {Grolmusz, Vince},
      title = {Low rank co-diagonal matrices and {R}amsey graphs},
      journal = {Electron. J. Combin.},
      fjournal = {Electronic Journal of Combinatorics},
      volume = {7},
      year = {2000},
      pages = {Research Paper 15, 7},
      issn = {1077-8926},
      mrclass = {15A33 (05C50 05C55)},
      mrnumber = {1756284},
      url = {http://www.combinatorics.org/Volume_7/Abstracts/v7i1r15.html},
      zblnumber = {0939.05060},
      }
  • [GUV09] Go to document V. Guruswami, C. Umans, and S. Vadhan, "Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes," J. ACM, vol. 56, iss. 4, p. 20, 2009.
    @ARTICLE{GUV09,
      author = {Guruswami, Venkatesan and Umans, Christopher and Vadhan, Salil},
      title = {Unbalanced expanders and randomness extractors from {P}arvaresh-{V}ardy codes},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {56},
      year = {2009},
      number = {4},
      pages = {Art. 20, 34},
      issn = {0004-5411},
      mrclass = {68R10 (05C85 05C90 68P30 68W20 94B99)},
      mrnumber = {2590822},
      mrreviewer = {Mark R. Jerrum},
      doi = {10.1145/1538902.1538904},
      url = {https://doi.org/10.1145/1538902.1538904},
      zblnumber = {1325.68169},
      }
  • [J90] Go to document S. Janson, "Poisson approximation for large deviations," Random Structures Algorithms, vol. 1, iss. 2, pp. 221-229, 1990.
    @ARTICLE{J90,
      author = {Janson, Svante},
      title = {Poisson approximation for large deviations},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {1},
      year = {1990},
      number = {2},
      pages = {221--229},
      issn = {1042-9832},
      mrclass = {60F10 (05C80 60C05)},
      mrnumber = {1138428},
      mrreviewer = {Andrew D. Barbour},
      doi = {10.1002/rsa.3240010209},
      url = {https://doi.org/10.1002/rsa.3240010209},
      zblnumber = {0747.05079},
      }
  • [intel] Go to document B. Jun and P. Kocher, The Intel random number generator, Cryptography Research Inc. white paper, 1999.
    @MISC{intel,
      author = {Jun, B. and Kocher, P.},
      title = {The {Intel} random number generator, {C}ryptography {R}esearch {I}nc. white paper},
      year = {1999},
      zblnumber = {},
      url = {https://42xtjqm0qj0382ac91ye9exr-wpengine.netdna-ssl.com/wp-content/uploads/2015/08/IntelRNG.pdf},
      }
  • [KKL88] Go to document J. Kahn, G. Kalai, and N. Linial, "The influence of variables on Boolean functions (extended abstract)," in The 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, , 1988, pp. 68-80.
    @INCOLLECTION{KKL88,
      author = {Kahn, J. and Kalai, G. and Linial, N.},
      title = {The influence of variables on {B}oolean functions (extended abstract)},
      booktitle = {The 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988},
      year = {1988},
      pages = {68--80},
      zblnumber = {},
      doi = {10.1109/SFCS.1988.21923},
      }
  • [klr] Go to document Y. T. Kalai, X. Li, and A. Rao, "2-source extractors under computational assumptions and cryptography with defective randomness," in 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 617-626.
    @INCOLLECTION{klr,
      author = {Kalai, Yael Tauman and Li, Xin and Rao, Anup},
      title = {2-source extractors under computational assumptions and cryptography with defective randomness},
      booktitle = {2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2009},
      pages = {617--626},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2009},
      mrclass = {94A60 (68Q87)},
      mrnumber = {2648439},
      doi = {10.1109/FOCS.2009.61},
      url = {https://doi.org/10.1109/FOCS.2009.61},
      zblnumber = {1292.94088},
      }
  • [klrz] Go to document Y. T. Kalai, X. Li, A. Rao, and D. Zuckerman, "Network extractor protocols," in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, 2008, pp. 654-663.
    @INCOLLECTION{klrz,
      author = {Kalai, Yael Tauman and Li, Xin and Rao, Anup and Zuckerman, D.},
      title = {Network extractor protocols},
      booktitle = {Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science},
      year = {2008},
      pages = {654--663},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      zblnumber = {},
      doi = {10.1109/FOCS.2008.73},
      }
  • [Li11] Go to document X. Li, "Improved constructions of three source extractors," in 26th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 126-136.
    @INCOLLECTION{Li11,
      author = {Li, Xin},
      title = {Improved constructions of three source extractors},
      booktitle = {26th {A}nnual {IEEE} {C}onference on {C}omputational {C}omplexity},
      pages = {126--136},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2011},
      mrclass = {68Q87 (68W20)},
      mrnumber = {3025367},
      zblnumber = {},
      doi = {10.1109/CCC.2011.26},
      }
  • [Li12a] Go to document X. Li, "Design extractors, non-malleable condensers and privacy amplification," in STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 837-854.
    @INCOLLECTION{Li12a,
      author = {Li, Xin},
      title = {Design extractors, non-malleable condensers and privacy amplification},
      booktitle = {S{TOC}'12---{P}roceedings of the 2012 {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {837--854},
      publisher = {ACM, New York},
      year = {2012},
      mrclass = {68Q85 (68M12 94C30)},
      mrnumber = {2961549},
      doi = {10.1145/2213977.2214052},
      url = {https://doi.org/10.1145/2213977.2214052},
      zblnumber = {1286.94077},
      }
  • [Li12b] Go to document X. Li, "Non-malleable extractors, two-source extractors and privacy amplification," in 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 688-697.
    @INCOLLECTION{Li12b,
      author = {Li, Xin},
      title = {Non-malleable extractors, two-source extractors and privacy amplification},
      booktitle = {2012 {IEEE} 53rd {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2012},
      pages = {688--697},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2012},
      mrclass = {68Q87 (68M12 94A60 94A62)},
      mrnumber = {3186657},
      zblnumber = {},
      doi = {10.1109/FOCS.2012.26},
      }
  • [Li13b] Go to document X. Li, "Extractors for a constant number of independent sources with polylogarithmic min-entropy," in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 100-109.
    @INCOLLECTION{Li13b,
      author = {Li, Xin},
      title = {Extractors for a constant number of independent sources with polylogarithmic min-entropy},
      booktitle = {2013 {IEEE} 54th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2013},
      pages = {100--109},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2013},
      mrclass = {68W20},
      mrnumber = {3246211},
      doi = {10.1109/FOCS.2013.19},
      url = {https://doi.org/10.1109/FOCS.2013.19},
      zblnumber = {},
      }
  • [Li13a] Go to document X. Li, "New independent source extractors with exponential improvement," in STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 783-792.
    @INCOLLECTION{Li13a,
      author = {Li, Xin},
      title = {New independent source extractors with exponential improvement},
      booktitle = {S{TOC}'13---{P}roceedings of the 2013 {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {783--792},
      publisher = {ACM, New York},
      year = {2013},
      mrclass = {68Q87 (68Q01)},
      mrnumber = {3210840},
      doi = {10.1145/2488608.2488708},
      url = {https://doi.org/10.1145/2488608.2488708},
      zblnumber = {1293.68059},
      }
  • [Li15c] Go to document X. Li, "Three-source extractors for polylogarithmic min-entropy," in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 863-882.
    @INCOLLECTION{Li15c,
      author = {Li, Xin},
      title = {Three-source extractors for polylogarithmic min-entropy},
      booktitle = {2015 {IEEE} 56th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2015},
      pages = {863--882},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2015},
      mrclass = {62B10 (68Q87)},
      mrnumber = {3473345},
      zblnumber = {},
      doi = {10.1109/FOCS.2015.58},
      }
  • [Li:affine] Go to document X. Li, "Improved two-source extractors, and affine extractors for polylogarithmic entropy," in 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 168-177.
    @INCOLLECTION{Li:affine,
      author = {Li, Xin},
      title = {Improved two-source extractors, and affine extractors for polylogarithmic entropy},
      booktitle = {57th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2016},
      pages = {168--177},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2016},
      mrclass = {68Q87 (62B10)},
      mrnumber = {3630977},
      zblnumber = {},
      doi = {10.1109/FOCS.2016.26},
      }
  • [li2017improved] Go to document X. Li, "Improved non-malleable extractors, non-malleable codes and independent source extractors," in STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 1144-1156.
    @INCOLLECTION{li2017improved,
      author = {Li, Xin},
      title = {Improved non-malleable extractors, non-malleable codes and independent source extractors},
      booktitle = {S{TOC}'17---{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {1144--1156},
      publisher = {ACM, New York},
      year = {2017},
      mrclass = {94B05},
      mrnumber = {3678258},
      zblnumber = {1370.94527},
      doi = {10.1145/3055399.3055486},
      }
  • [Li18] X. Li, Non-malleable extractors and non-malleable codes: Partially optimal constructions, 2018.
    @MISC{Li18,
      author = {Li, Xin},
      title = {Non-malleable extractors and non-malleable codes: {P}artially optimal constructions},
      arxiv = {1804.04005},
      year = {2018},
      zblnumber = {},
      }
  • [LRVW03] Go to document C. Lu, O. Reingold, S. Vadhan, and A. Wigderson, "Extractors: optimal up to constant factors," in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, 2003, pp. 602-611.
    @INPROCEEDINGS{LRVW03,
      author = {Lu, Chi-Jen and Reingold, Omer and Vadhan, Salil and Wigderson, Avi},
      title = {Extractors: optimal up to constant factors},
      booktitle = {Proceedings of the {T}hirty-{F}ifth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {602--611},
      publisher = {ACM, New York},
      year = {2003},
      mrclass = {68W20 (65C10 68Q25 94B60)},
      mrnumber = {2120441},
      doi = {10.1145/780542.780630},
      url = {https://doi.org/10.1145/780542.780630},
      zblnumber = {1192.68859},
      }
  • [Mek:resil] R. Meka, Explicit Coin Flipping Protocols, 2009.
    @MISC{Mek:resil,
      author = {Meka, Raghu},
      title = {Explicit Coin Flipping Protocols},
      note = {unpublished manuscript},
      year = {2009},
      zblnumber = {},
      }
  • [Mek:resilient] Go to document R. Meka, "Explicit resilient functions matching Ajtai-Linial," in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 1132-1148.
    @INPROCEEDINGS{Mek:resilient,
      author = {Meka, Raghu},
      title = {Explicit resilient functions matching {A}jtai-{L}inial},
      booktitle = {Proceedings of the {T}wenty-{E}ighth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      pages = {1132--1148},
      publisher = {SIAM, Philadelphia, PA},
      year = {2017},
      mrclass = {68R05 (68Q25)},
      mrnumber = {3627802},
      doi = {10.1137/1.9781611974782.73},
      url = {https://doi.org/10.1137/1.9781611974782.73},
      zblnumber = {06904101},
      }
  • [NZ96] Go to document N. Nisan and D. Zuckerman, "Randomness is linear in space," J. Comput. System Sci., vol. 52, iss. 1, pp. 43-52, 1996.
    @ARTICLE{NZ96,
      author = {Nisan, Noam and Zuckerman, David},
      title = {Randomness is linear in space},
      journal = {J. Comput. System Sci.},
      fjournal = {Journal of Computer and System Sciences},
      volume = {52},
      year = {1996},
      number = {1},
      pages = {43--52},
      issn = {0022-0000},
      mrclass = {68Q05 (68Q15)},
      mrnumber = {1375803},
      mrreviewer = {Mark R. Jerrum},
      doi = {10.1006/jcss.1996.0004},
      url = {https://doi.org/10.1006/jcss.1996.0004},
      zblnumber = {0846.68041},
      }
  • [PR04] P. Pudlák and V. Rödl, "Pseudorandom sets and explicit constructions of Ramsey graphs," in Complexity of Computations and Proofs, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, vol. 13, pp. 327-346.
    @INCOLLECTION{PR04,
      author = {Pudl\'{a}k, Pavel and Rödl, Vojtěch},
      title = {Pseudorandom sets and explicit constructions of {R}amsey graphs},
      booktitle = {Complexity of Computations and Proofs},
      series = {Quad. Mat.},
      volume = {13},
      pages = {327--346},
      publisher = {Dept. Math., Seconda Univ. Napoli, Caserta},
      year = {2004},
      mrclass = {05C80 (05D10 68Q17)},
      mrnumber = {2131412},
      mrreviewer = {David B. Penman},
      zblnumber = {1074.05088},
      }
  • [Ram] Go to document F. P. Ramsey, "On a Problem of Formal Logic," Proc. London Math. Soc. (2), vol. 30, iss. 4, pp. 264-286, 1929.
    @ARTICLE{Ram,
      author = {Ramsey, F. P.},
      title = {On a {P}roblem of {F}ormal {L}ogic},
      journal = {Proc. London Math. Soc. (2)},
      fjournal = {Proceedings of the London Mathematical Society. Second Series},
      volume = {30},
      year = {1929},
      number = {4},
      pages = {264--286},
      issn = {0024-6115},
      mrclass = {DML},
      mrnumber = {1576401},
      doi = {10.1112/plms/s2-30.1.264},
      url = {https://doi.org/10.1112/plms/s2-30.1.264},
      jfmnumber = {55.0032.04},
      }
  • [Rao06] Go to document A. Rao, "Extractors for a constant number of polynomially small min-entropy independent sources," SIAM J. Comput., vol. 39, iss. 1, pp. 168-194, 2009.
    @ARTICLE{Rao06,
      author = {Rao, Anup},
      title = {Extractors for a constant number of polynomially small min-entropy independent sources},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {39},
      year = {2009},
      number = {1},
      pages = {168--194},
      issn = {0097-5397},
      mrclass = {68Q87 (05C55 05C65)},
      mrnumber = {2506523},
      mrreviewer = {Domingos Dellamonica, Jr.},
      doi = {10.1137/060671218},
      url = {https://doi.org/10.1137/060671218},
      zblnumber = {1185.68453},
      }
  • [Rao09] Go to document A. Rao, "Extractors for low-weight affine sources," in 24th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 95-101.
    @INCOLLECTION{Rao09,
      author = {Rao, Anup},
      title = {Extractors for low-weight affine sources},
      booktitle = {24th {A}nnual {IEEE} {C}onference on {C}omputational {C}omplexity},
      pages = {95--101},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2009},
      mrclass = {68Q87 (94A60)},
      mrnumber = {2932458},
      doi = {10.1109/CCC.2009.36},
      url = {https://doi.org/10.1109/CCC.2009.36},
      zblnumber = {},
      }
  • [RZ08] Go to document A. Rao and D. Zuckerman, "Extractors for three uneven-length sources," in Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, Springer, Cham, 2008, vol. 5171, pp. 557-570.
    @INCOLLECTION{RZ08,
      author = {Rao, Anup and Zuckerman, D.},
      title = {Extractors for three uneven-length sources},
      booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, {APPROX} 2008, and 12th International Workshop, {RANDOM} 2008, Boston, MA, USA, August 25-27, 2008. Proceedings},
      series = {Lecture Notes in Computer Science},
      volume = {5171},
      publisher = {Springer, Cham},
      year = {2008},
      pages = {557--570},
      zblnumber = {1159.68654},
      doi = {10.1007/978-3-540-85363-3_44},
      }
  • [Raz05] Go to document R. Raz, "Extractors with weak random seeds," in STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 11-20.
    @INCOLLECTION{Raz05,
      author = {Raz, Ran},
      title = {Extractors with weak random seeds},
      booktitle = {S{TOC}'05: {P}roceedings of the 37th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {11--20},
      publisher = {ACM, New York},
      year = {2005},
      mrclass = {68Q25 (68R10 68W20)},
      mrnumber = {2181597},
      doi = {10.1145/1060590.1060593},
      url = {https://doi.org/10.1145/1060590.1060593},
      zblnumber = {1192.68373},
      }
  • [RRV02] Go to document R. Raz, O. Reingold, and S. Vadhan, "Extracting all the randomness and reducing the error in Trevisan’s extractors," J. Comput. System Sci., vol. 65, iss. 1, pp. 97-128, 2002.
    @ARTICLE{RRV02,
      author = {Raz, Ran and Reingold, Omer and Vadhan, Salil},
      title = {Extracting all the randomness and reducing the error in {T}revisan's extractors},
      note = {Special issue on STOC, 1999 (Atlanta, GA)},
      journal = {J. Comput. System Sci.},
      fjournal = {Journal of Computer and System Sciences},
      volume = {65},
      year = {2002},
      number = {1},
      pages = {97--128},
      issn = {0022-0000},
      mrclass = {68P30 (68R10 68W20 68W40)},
      mrnumber = {1946290},
      doi = {10.1006/jcss.2002.1824},
      url = {https://doi.org/10.1006/jcss.2002.1824},
      zblnumber = {1020.68029},
      }
  • [RZ01] Go to document A. Russell and D. Zuckerman, "Perfect information leader election in ${ log}^\ast n+O(1)$ rounds," J. Comput. System Sci., vol. 63, iss. 4, pp. 612-626, 2001.
    @ARTICLE{RZ01,
      author = {Russell, Alexander and Zuckerman, David},
      title = {Perfect information leader election in {${\rm log}^\ast n+O(1)$} rounds},
      note = {Special issue on FOCS 98 (Palo Alto, CA)},
      journal = {J. Comput. System Sci.},
      fjournal = {Journal of Computer and System Sciences},
      volume = {63},
      year = {2001},
      number = {4},
      pages = {612--626},
      issn = {0022-0000},
      mrclass = {68Q85 (68W15 91A40 91B12)},
      mrnumber = {1894524},
      mrreviewer = {Fouad T. Aleskerov},
      doi = {10.1006/jcss.2001.1776},
      url = {https://doi.org/10.1006/jcss.2001.1776},
      zblnumber = {1006.68012},
      }
  • [SV86] Go to document M. Sántha and U. V. Vazirani, "Generating quasi-random sequences from semi-random sources," J. Comput. System Sci., vol. 33, iss. 1, pp. 75-87, 1986.
    @ARTICLE{SV86,
      author = {S\'{a}ntha, Miklós and Vazirani, Umesh V.},
      title = {Generating quasi-random sequences from semi-random sources},
      note = {Twenty-fifth annual symposium on foundations of computer science (Singer Island, Fla., 1984)},
      journal = {J. Comput. System Sci.},
      fjournal = {Journal of Computer and System Sciences},
      volume = {33},
      year = {1986},
      number = {1},
      pages = {75--87},
      issn = {0022-0000},
      mrclass = {68Q99 (65C10 68Q25 68U20)},
      mrnumber = {0864080},
      doi = {10.1016/0022-0000(86)90044-9},
      url = {https://doi.org/10.1016/0022-0000(86)90044-9},
      zblnumber = {},
      }
  • [Sha02] R. Shaltiel, "Recent developments in explicit constructions of extractors," Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, iss. 77, pp. 67-95, 2002.
    @ARTICLE{Sha02,
      author = {Shaltiel, Ronen},
      title = {Recent developments in explicit constructions of extractors},
      journal = {Bull. Eur. Assoc. Theor. Comput. Sci. EATCS},
      fjournal = {Bulletin of the European Association for Theoretical Computer Science. EATCS},
      number = {77},
      year = {2002},
      pages = {67--95},
      issn = {0252-9742},
      mrclass = {68Q25 (68W20)},
      mrnumber = {1920329},
      zblnumber = {1051.68070},
      }
  • [Shaltiel08] Go to document R. Shaltiel, "How to get more mileage from randomness extractors," Random Structures Algorithms, vol. 33, iss. 2, pp. 157-186, 2008.
    @ARTICLE{Shaltiel08,
      author = {Shaltiel, Ronen},
      title = {How to get more mileage from randomness extractors},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {33},
      year = {2008},
      number = {2},
      pages = {157--186},
      issn = {1042-9832},
      mrclass = {60E05 (60E10)},
      mrnumber = {2436845},
      doi = {10.1002/rsa.20207},
      url = {https://doi.org/10.1002/rsa.20207},
      zblnumber = {1181.68170},
      }
  • [sipser1988expanders] Go to document M. Sipser, "Expanders, randomness, or time versus space," J. Comput. System Sci., vol. 36, iss. 3, pp. 379-383, 1988.
    @ARTICLE{sipser1988expanders,
      author = {Sipser, Michael},
      title = {Expanders, randomness, or time versus space},
      note = {Structure in Complexity Theory Conference (Berkeley, CA, 1986)},
      journal = {J. Comput. System Sci.},
      fjournal = {Journal of Computer and System Sciences},
      volume = {36},
      year = {1988},
      number = {3},
      pages = {379--383},
      issn = {0022-0000},
      mrclass = {68Q15 (05C99)},
      mrnumber = {0973446},
      mrreviewer = {William Gasarch},
      doi = {10.1016/0022-0000(88)90035-9},
      url = {https://doi.org/10.1016/0022-0000(88)90035-9},
      zblnumber = {0652.68050},
      }
  • [Tal15] Go to document A. Tal, "Tight bounds on the Fourier spectrum of ${\bf{AC}}^{\bf 0}$," in 32nd Computational Complexity Conference, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, vol. 79, p. 15.
    @INCOLLECTION{Tal15,
      author = {Tal, Avishay},
      title = {Tight bounds on the {F}ourier spectrum of {${\bf{AC}}^{\bf 0}$}},
      booktitle = {32nd {C}omputational {C}omplexity {C}onference},
      series = {LIPIcs. Leibniz Int. Proc. Inform.},
      volume = {79},
      pages = {Art. No. 15, 31},
      publisher = {Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern},
      year = {2017},
      mrclass = {94C05 (68Q25)},
      mrnumber = {3691140},
      mrreviewer = {Martin C. Cooper},
      zblnumber = {},
      doi = {10.4230/LIPIcs.CCC.2017.15},
      }
  • [Tr01] Go to document L. Trevisan, "Extractors and pseudorandom generators," J. ACM, vol. 48, iss. 4, pp. 860-879, 2001.
    @ARTICLE{Tr01,
      author = {Trevisan, Luca},
      title = {Extractors and pseudorandom generators},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {48},
      year = {2001},
      number = {4},
      pages = {860--879},
      issn = {0004-5411},
      mrclass = {68P30 (65C10 68W20)},
      mrnumber = {2144932},
      doi = {10.1145/502090.502099},
      url = {https://doi.org/10.1145/502090.502099},
      zblnumber = {1127.68403},
      }
  • [Viola14] Go to document E. Viola, "Extractors for circuit sources," SIAM J. Comput., vol. 43, iss. 2, pp. 655-672, 2014.
    @ARTICLE{Viola14,
      author = {Viola, Emanuele},
      title = {Extractors for circuit sources},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {43},
      year = {2014},
      number = {2},
      pages = {655--672},
      issn = {0097-5397},
      mrclass = {68Q17},
      mrnumber = {3504677},
      doi = {10.1137/11085983X},
      url = {https://doi.org/10.1137/11085983X},
      zblnumber = {1301.68195},
      }
  • [Z97] Go to document D. Zuckerman, "Randomness-optimal oblivious sampling," in Proceedings of the Workshop on Randomized Algorithms and Computation, 1997, pp. 345-367.
    @INPROCEEDINGS{Z97,
      author = {Zuckerman, David},
      title = {Randomness-optimal oblivious sampling},
      booktitle = {Proceedings of the {W}orkshop on {R}andomized {A}lgorithms and {C}omputation},
      venue = {{B}erkeley, {CA},
      1995},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {11},
      year = {1997},
      number = {4},
      pages = {345--367},
      issn = {1042-9832},
      mrclass = {68Q05 (65C10 68Q15)},
      mrnumber = {1608823},
      mrreviewer = {Hsien-Kuei Hwang},
      zblnumber = {0891.60100},
      url = {http://doi.org/cr8kht},
      }

Authors

Eshan Chattopadhyay

Department of Computer Science, Cornell University, Ithaca, NY

David Zuckerman

Department of Computer Science, University of Texas at Austin, Austin, TX