research-article

Extractors and Lower Bounds for Locally Samplable Sources

Authors:

Thomas WatsonAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 4, Issue 1

Article No.: 3, Pages 1 - 21

https://doi.org/10.1145/2141938.2141941

Published: 01 March 2012 Publication History

Abstract

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number d of the random input bits. As our main result, we construct a deterministic extractor that, given any d-local source with min-entropy k on n bits, extracts Ω(k²/nd) bits that are 2^−nΩ(1)-close to uniform, provided d ≤ o(log n) and k ≥ n^2/3+γ (for arbitrarily small constants γ > 0).

Using our result, we also improve a result of Viola [2010] who proved a 1/2 − O(1/log n) statistical distance lower bound for o(log n)-local samplers trying to sample input-output pairs of an explicit boolean function, assuming the samplers use at most n + n^1−δ random bits for some constant δ > 0. Using a different function, we simultaneously improve the lower bound to 1/2 − 2^−nΩ(1) and eliminate the restriction on the number of random bits.

References

[1]

Applebaum, B. 2011. Pseudorandom generators with long stretch and low locality from random local one-way functions. Tech. rep. TR11-007, Electronic Colloquium on Computational Complexity.

[2]

Applebaum, B., Ishai, Y., and Kushilevitz, E. 2006. Cryptography in NC⁰. SIAM J. Comput. 36, 4, 845--888.

Digital Library

[3]

Applebaum, B., Ishai, Y., and Kushilevitz, E. 2008. On pseudorandom generators with linear stretch in NC⁰. Comput. Complex. 17, 1, 38--69.

Digital Library

[4]

Applebaum, B., Bogdanov, A., and Rosen, A. 2011. A dichotomy for local small-bias generators. Tech. rep. TR11-126, Electronic Colloquium on Computational Complexity.

[5]

Arora, S., Steurer, D., and Wigderson, A. 2009. Towards a study of low-complexity graphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming. 119--131.

Digital Library

[6]

Barak, B., Impagliazzo, R., and Wigderson, A. 2006a. Extracting randomness using few independent sources. SIAM J. Comput. 36, 4, 1095--1118.

Digital Library

[7]

Barak, B., Rao, A., Shaltiel, R., and Wigderson, A. 2006b. 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. In Proceedings of the 38th ACM Symposium on Theory of Computing. 671--680.

Digital Library

[8]

Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., and Wigderson, A. 2010. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM 57, 4.

Digital Library

[9]

Bellare, M. and Rompel, J. 1994. Randomness-efficient oblivious sampling. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. 276--287.

Digital Library

[10]

Ben-Sasson, E. and Gabizon, A. 2011. Extractors for polynomials sources over constant-size fields of small characteristic. Tech. rep. TR11-129, Electronic Colloquium on Computational Complexity.

[11]

Bogdanov, A. and Qiao, Y. 2009. On the security of Goldreich’s one-way function. In Proceedings of the 13th International Workshop on Randomization and Computation. 392--405.

Digital Library

[12]

Bourgain, J. 2005. More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 1, 1--32.

[13]

Bourgain, J. 2007. On the construction of affine-source extractors. Geom. Funct. Anal. 1, 33--57.

[14]

Chor, B. and Goldreich, O. 1988. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17, 2, 230--261.

Digital Library

[15]

Chor, B., Friedman, J., Goldreich, O., Håstad, J., Rudich, S., and Smolensky, R. 1985. The bit extraction problem or t-resilient functions. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. 396--407.

Digital Library

[16]

Cook, J., Etesami, O., Miller, R., and Trevisan, L. 2009. Goldreich’s one-way function candidate and myopic backtracking algorithms. In Proceedings of the 6th Theory of Cryptography Conference. 521--538.

Digital Library

[17]

Cryan, M. and Miltersen, P. B. 2001. On pseudorandom generators in NC⁰. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science. 272--284.

Digital Library

[18]

De, A. and Trevisan, L. 2009. Extractors using hardness amplification. In Proceedings of the 13th International Workshop on Randomization and Computation. 462--475.

Digital Library

[19]

DeVos, M. and Gabizon, A. 2010. Simple affine extractors using dimension expansion. In Proceedings of the 25th IEEE Conference on Computational Complexity. 50--57.

Digital Library

[20]

Dodis, Y., Elbaz, A., Oliveira, R., and Raz, R. 2004. Improved randomness extraction from two independent sources. In Proceedings of the 8th International Workshop on Randomization and Computation. 334--344.

[21]

Dvir, Z. 2009. Extractors for varieties. In Proceedings of the 24th IEEE Conference on Computational Complexity. 102--113.

Digital Library

[22]

Dvir, Z., Gabizon, A., and Wigderson, A. 2009. Extractors and rank extractors for polynomial sources. Comput. Complex. 18, 1, 1--58.

Digital Library

[23]

Dziembowski, S. and Maurer, U. 2004. Optimal randomizer efficiency in the bounded-storage model. J. Cryptol. 17, 1, 5--26.

Digital Library

[24]

Gabizon, A. and Raz, R. 2008. Deterministic extractors for affine sources over large fields. Combinatorica 28, 4, 415--440.

Digital Library

[25]

Gabizon, A., Raz, R., and Shaltiel, R. 2006. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. Comput. 36, 4, 1072--1094.

Digital Library

[26]

Goldreich, O. 2011. Candidate one-way functions based on expander graphs. Studies Complex. Cryptograph., 76--87.

[27]

Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., and Rothblum, G. 2007. Verifying and decoding in constant depth. In Proceedings of the 39th ACM Symposium on Theory of Computing. 440--449.

Digital Library

[28]

Guruswami, V. and Rudra, A. 2008. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Inf. Theory 54, 1, 135--150.

Digital Library

[29]

Guruswami, V., Umans, C., and Vadhan, S. 2009. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56, 4.

Digital Library

[30]

Håstad, J. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th ACM Symposium on Theory of Computing. 6--20.

Digital Library

[31]

Håstad, J. 1987. One-way permutations in NC⁰. Inf. Process. Lett. 26, 3, 153--155.

Digital Library

[32]

Ishai, Y., Kushilevitz, E., Ostrovsky, R., and Sahai, A. 2008. Cryptography with constant computational overhead. In Proceedings of the 40th ACM Symposium on Theory of Computing. 433--442.

Digital Library

[33]

Kamp, J. and Zuckerman, D. 2007. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36, 5, 1231--1247.

Digital Library

[34]

Kamp, J., Rao, A., Vadhan, S., and Zuckerman, D. 2011. Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77, 1, 191--220.

Digital Library

[35]

Li, X. 2011a. Improved constructions of three source extractors. In Proceedings of the 26th IEEE Conference on Computational Complexity. 126--136.

Digital Library

[36]

Li, X. 2011b. A new approach to affine extractors and dispersers. In Proceedings of the 26th IEEE Conference on Computational Complexity. 137--147.

Digital Library

[37]

Lovett, S. and Viola, E. 2011. Bounded-depth circuits cannot sample good codes. In Proceedings of the 26th IEEE Conference on Computational Complexity. 243--251.

Digital Library

[38]

Lu, C.-J. 2004. Encryption against storage-bounded adversaries from on-line strong extractors. J. Cryptol. 17, 1, 27--42.

Digital Library

[39]

Mossel, E., Shpilka, A., and Trevisan, L. 2006. On epsilon-biased generators in NC⁰. Random Struct. Algor. 29, 1, 56--81.

Digital Library

[40]

Nisan, N. and Zuckerman, D. 1996. Randomness is linear in space. J. Comput. Syst. Sci. 52, 1, 43--52.

Digital Library

[41]

Rao, A. 2008. A 2-source almost-extractor for linear entropy. In Proceedings of the 12th International Workshop on Randomization and Computation. 549--556.

Digital Library

[42]

Rao, A. 2009a. Extractors for a constant number of polynomially small min-entropy independent sources. SIAM J. Comput. 39, 1, 168--194.

Digital Library

[43]

Rao, A. 2009b. Extractors for low-weight affine sources. In Proceedings of the 24th IEEE Conference on Computational Complexity. 95--101.

Digital Library

[44]

Rao, A. and Zuckerman, D. 2008. Extractors for three uneven-length sources. In Proceedings of the 12th International Workshop on Randomization and Computation. 557--570.

Digital Library

[45]

Raz, R. 2005. Extractors with weak random seeds. In Proceedings of the 37th ACM Symposium on Theory of Computing. 11--20.

Digital Library

[46]

Raz, R. and Yehudayoff, A. 2011. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Syst. Sci. 77, 1, 167--190.

Digital Library

[47]

Raz, R., Reingold, O., and Vadhan, S. 1999. Error reduction for extractors. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. 191--201.

Digital Library

[48]

Raz, R., Reingold, O., and Vadhan, S. 2002. Extracting all the randomness and reducing the error in Trevisan’s extractors. J. Comput. Syst. Sci. 65, 1, 97--128.

Digital Library

[49]

Schmidt, J., Siegel, A., and Srinivasan, A. 1995. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discr. Math. 8, 2, 223--250.

Digital Library

[50]

Shaltiel, R. 2002. Recent developments in explicit constructions of extractors. Bull. Euro. Assoc. Theor. Comput. Sci. 77, 67--95.

[51]

Shaltiel, R. 2008. How to get more mileage from randomness extractors. Random Struct. Algor. 33, 2, 157--186.

Digital Library

[52]

Shaltiel, R. 2011. An introduction to randomness extractors. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming. 21--41.

Digital Library

[53]

Shoup, V. 1988. New algorithms for finding irreducible polynomials over finite fields. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science. 283--290.

Digital Library

[54]

Sudan, M. 2002. Essential coding theory---Course notes. http://theory.lcs.mit.edu/~madhu/coding/.

[55]

Tauman Kalai, Y., Li, X., and Rao, A. 2009. 2-source extractors under computational assumptions and cryptography with defective randomness. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science. 617--626.

Digital Library

[56]

Trevisan, L. 2001. Extractors and pseudorandom generators. J. ACM 48, 4, 860--879.

Digital Library

[57]

Trevisan, L. and Vadhan, S. 2000. Extracting randomness from samplable distributions. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science. 32--42.

Digital Library

[58]

Vadhan, S. 2004. Constructing locally computable extractors and cryptosystems in the bounded-storage model. J. Cryptol. 17, 1, 43--77.

Digital Library

[59]

Vadhan, S. 2011. Pseudorandomness. In Foundations and Trends in Theoretical Computer Science. To appear.

Digital Library

[60]

Viola, E. 2010. The complexity of distributions. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science. 202--211.

Digital Library

[61]

Viola, E. 2011. Extractors for circuit sources. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science. To appear.

Digital Library

[62]

Yao, A. 1985. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science. 1--10.

Digital Library

[63]

Yehudayoff, A. 2011. Affine extractors over prime fields. Combinatorica 31, 2, 245--256.

Digital Library

[64]

Zimand, M. 2010. Simple extractors via constructions of cryptographic pseudo-random generators. Theor. Comput. Sci. 411, 10, 1236--1250.

Digital Library

Cited By

Kane DOstuni AWu KMohar BShinkar IO'Donnell R(2024)Locality Bounds for Sampling Hamming SlicesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649670(1279-1286)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649670
Doron DMoshkovitz DOh JZuckerman DSaha BServedio R(2023)Almost Chor-Goldreich Sources and Adversarial Random WalksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585134(1-9)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585134
Ilango RRen HSanthanam RLeonardi SGupta A(2022)Robustness of average-case meta-complexity via pseudorandomnessProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520051(1575-1583)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520051
Show More Cited By

Index Terms

Extractors and Lower Bounds for Locally Samplable Sources
1. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Extractors with weak random seeds
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
We show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. Our main results are as follows:
- A long line of research, ...
Extractors and lower bounds for locally samplable sources
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number d of the random input bits. As our main result, we construct a deterministic ...
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography

We give an efficient deterministic algorithm that extracts $\Omega(n^{2\gamma})$ almost-random bits from sources where $n^{\frac{1}{2}+\gamma}$ of the $n$ bits are uniformly random and the rest are fixed in advance. This improves upon previous ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 4, Issue 1

March 2012

76 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2141938

Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2012

Accepted: 01 December 2011

Revised: 01 October 2011

Received: 01 July 2011

Published in TOCT Volume 4, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
224
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kane DOstuni AWu KMohar BShinkar IO'Donnell R(2024)Locality Bounds for Sampling Hamming SlicesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649670(1279-1286)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649670
Doron DMoshkovitz DOh JZuckerman DSaha BServedio R(2023)Almost Chor-Goldreich Sources and Adversarial Random WalksProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585134(1-9)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585134
Ilango RRen HSanthanam RLeonardi SGupta A(2022)Robustness of average-case meta-complexity via pseudorandomnessProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520051(1575-1583)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520051
Göös MWatson T(2020)A Lower Bound for Sampling Disjoint SetsACM Transactions on Computation Theory10.1145/340485812:3(1-13)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3404858
Yasunaga K(2018)Error Correction by Structural Simplicity: Correcting Samplable Additive ErrorsThe Computer Journal10.1093/comjnl/bxy100Online publication date: 5-Oct-2018
https://doi.org/10.1093/comjnl/bxy100
Viola E(2016)Quadratic Maps Are Hard to SampleACM Transactions on Computation Theory10.1145/29343088:4(1-4)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2934308
Watson T(2014)Time Hierarchies for Sampling DistributionsSIAM Journal on Computing10.1137/12089855343:5(1709-1727)Online publication date: Jan-2014
https://doi.org/10.1137/120898553
Viola E(2014)Extractors for Circuit SourcesSIAM Journal on Computing10.1137/11085983X43:2(655-672)Online publication date: Jan-2014
https://doi.org/10.1137/11085983X
Yasunaga K(2014)Correction of samplable additive errors2014 IEEE International Symposium on Information Theory10.1109/ISIT.2014.6874996(1066-1070)Online publication date: Jun-2014
https://doi.org/10.1109/ISIT.2014.6874996
Watson TKleinberg R(2013)Time hierarchies for sampling distributionsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422484(429-440)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422484
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents