Pseudorandomness and Combinatorial Constructions

zbMATH Open1100.68031arXivcs/0601100MaRDI QIDQ5491027FDOQ5491027

Authors: Luca Trevisan 

Publication date: 26 September 2006

Abstract: In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known deterministic algorithms for the same problem. Despite this evidence for the power of random choices, the computational theory of pseudorandomness shows that, under certain complexity-theoretic assumptions, every probabilistic algorithm has an efficient deterministic simulation and a large class of applications of the the probabilistic method can be converted into explicit constructions. In this survey paper we describe connections between the conditional ``derandomization results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and ``randomness extractors.

Full work available at URL: https://arxiv.org/abs/cs/0601100

Recommendations

• scientific article; zbMATH DE number 1195809
• Pseudo-randomness: objects and generation
• The complexity of explicit constructions
• The complexity of explicit constructions
• Pseudorandomness

zbMATH Keywords

derandomizationpseudorandomnessrandomness extractionComputational complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (13)

• Pseudo-randomness: objects and generation
• Pseudorandom generators for combinatorial checkerboards
• Number-theoretic constructions of efficient pseudo-random functions
• Title not available (Why is that?)
• The complexity of explicit constructions
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Title not available (Why is that?)
• Pseudorandom generators for combinatorial shapes
• The determinism of randomness and its use in combinatorics
• Pseudorandomness in computer science and in additive combinatorics
• Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
• Generation of all randomizations using circuits
• The complexity of explicit constructions

This page was built for publication: Pseudorandomness and Combinatorial Constructions

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