1992/01/01 by Noga Alon, Oded Goldreich, Johan Håstad +1 · 569 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Limits and Structures in Graph Theory #Mathematics #Simple (philosophy) #Combinatorics #Distribution (mathematics) #Discrete mathematics #Binary logarithm #Upper and lower bounds #Random variable #Log-log plot #Point (geometry) #Space (punctuation) #Statistics #Mathematical analysis #Computer science #Geometry
paper · doi:10.1002/rsa.3240030308
published in Random Structures and Algorithms 3(3), 289-304 (Wiley)
openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
Abstract We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o (1)) (log log n + k /2 + log k + log 1/ϵ), where ϵ is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ϵ < 1/( k log n )). An additional advantage of our constructions is their simplicity.