Simulating independence

DOI10.1145/1060590.1060592MaRDI QIDQ5901100zbMATH OpenOpenAlexFDO

Authors Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, A. Wigderson

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

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Generalized Ramsey theory (05C55)

Recommendations

• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
• Constructions of independent sets in random intersection graphs
• Automata, Languages and Programming
• On the independent set problem in random graphs
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Towards optimal two-source extractors and Ramsey graphs
• On the concentration of the independence numbers of random hypergraphs
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers

Cited in

(24)

• Lossless condensers, unbalanced expanders, and extractors
• The sum-product theorem in Z_q with q arbitrary
• Deterministic extractors for affine sources over large fields
• A bipartite analogue of Dilworth's theorem
• Deterministic extractors for small-space sources
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Increasing the output length of zero-error dispersers
• From affine to two-source extractors via approximate duality
• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
• Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Non-malleable extractors and non-malleable codes: partially optimal constructions
• Zero-fixing extractors for sub-logarithmic entropy
• Local correlation breakers and applications to three-source extractors and mergers
• Extracting Randomness Using Few Independent Sources
• Explicit two-source extractors and resilient functions
• Extracting Computational Entropy and Learning Noisy Linear Functions
• Induced Ramsey-type theorems
• Explicit directional affine extractors and improved hardness for linear branching programs
• Two-source and affine non-malleable extractors for small entropy
• How to get more mileage from randomness extractors
• Increasing the Output Length of Zero-Error Dispersers

This page was built for publication: Simulating independence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901100)