Simulating independence

DOI10.1145/1060590.1060592zbMath1192.68468MaRDI QIDQ5901100

Avi Wigderson, Ronen Shaltiel, Guy Kindler, Boaz Barak, Benjamin Sudakov

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060592

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

05C55: Generalized Ramsey theory

68W20: Randomized algorithms

Related Items

Extracting Computational Entropy and Learning Noisy Linear Functions, Deterministic extractors for small-space sources, Induced Ramsey-type theorems, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Extracting Kolmogorov complexity with applications to dimension zero-one laws, A bipartite analogue of Dilworth's theorem, The sum-product theorem in \(\mathbb Z_q\) with \(q\) arbitrary, 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Deterministic extractors for affine sources over large fields, Increasing the output length of zero-error dispersers, How to get more mileage from randomness extractors, Increasing the Output Length of Zero-Error Dispersers, Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators