Pseudorandomness and Combinatorial Constructions

MaRDI QIDQ5491027zbMATH OpenFDO

Authors Luca Trevisan

Publication date 26 September 2006

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

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)

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.

Recommendations

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

Cited in

(13)

• Pseudorandom generators for combinatorial checkerboards
• Pseudo-randomness: objects and generation
• Number-theoretic constructions of efficient pseudo-random functions
• scientific article; zbMATH DE number 1195809 (Why is no real title available?)
• The complexity of explicit constructions
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• 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)