Randomness is Linear in Space

Open access

Nisan, Noam, Zuckerman, David·1996·Journal of Computer and System Sciences

DOI 10.1006/jcss.1996.0004

Open this paper in CoChat — free account

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

Integrity signals

Registry

Crossref · 10.1006/jcss.1996.0004

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Dodis, Y., Reyzin, L., & Smith, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_31 · Cited by 2,038
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
Message-Locked Encryption and Secure Deduplication
Bellare, M., Keelveedhi, S., & Ristenpart, T. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_18 · Cited by 632
Cryptographic Extraction and Key Derivation: The HKDF Scheme
Krawczyk, H. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_34 · Cited by 408
Linear degree extractors and the inapproximability of max clique and chromatic number
Zuckerman, D. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132612 · Cited by 398
Self-citation
Pseudorandom Generators without the XOR Lemma
Sudan, M., Trevisan, L., & Vadhan, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1730 · Cited by 393
RECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
SHALTIEL, R. (2004) · Current Trends in Theoretical Computer Science · doi:10.1142/9789812562494_0013 · Cited by 291
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
Cramer, R., Dodis, Y., Fehr, S., Padró, C., & Wichs, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_27 · Cited by 259
Extracting all the randomness and reducing the error in Trevisan's extractors
Raz, R., Reingold, O., & Vadhan, S. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301292 · Cited by 171
Trevisan's Extractor in the Presence of Quantum Side Information
De, A., Portmann, C., Vidick, T., & Renner, R. (2012) · SIAM Journal on Computing · doi:10.1137/100813683 · Cited by 161
The Bounded-Storage Model in the Presence of a Quantum Adversary
Konig, R. T., & Terhal, B. M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.913245 · Cited by 65
Extracting Randomness via Repeated Condensing
Reingold, O., Shaltiel, R., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539703431032 · Cited by 39
A modular framework for randomness extraction based on Trevisan's construction
Mauerer, W., Portmann, C., & Scholz, V. B. (2012) · arXiv · doi:10.48550/arxiv.1212.0520 · Cited by 23
Quantum-Proof Randomness Extractors via Operator Space Theory
Berta, M., Fawzi, O., & Scholz, V. B. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2627531 · Cited by 12
Variations on classical and quantum extractors
Berta, M., Fawzi, O., Scholz, V., & Szehr, O. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6875078 · Cited by 10
The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives
Nguyen, M.-H. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_25 · Cited by 7

Authors: Nisan, N., & Zuckerman, D.
Venue: Journal of Computer and System Sciences
Publisher: Elsevier BV
Published: 1996-02
Volume: 52
Issue: 1
Pages: 43-52
ISSN: 0022-0000 (ISSN-L)
DOI: 10.1006/jcss.1996.0004
OpenAlex: W2060474153
Cited by: 634
References: 0
FWCI: 9.79
Type: journal article
Language: en
Open access: bronze

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review