Algorithmic derandomization via complexity theory

DOI10.1145/509907.509996MaRDI QIDQ3579213zbMATH OpenOpenAlexFDO

Authors

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Cited in

(17)

• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• Deterministic discrepancy minimization
• A polynomial time approximation scheme for computing the supremum of Gaussian processes
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Circuit lower bounds from learning-theoretic approaches
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Deterministic parallel algorithms for bilinear objective functions
• Derandomizing logspace with a small shared hard drive
• Derandomizing logspace with a small shared hard drive
• Improved parallel derandomization via finite automata with applications

This page was built for publication: Algorithmic derandomization via complexity theory

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