Algorithmic derandomization via complexity theory

DOI10.1145/509907.509996zbMath1192.68303OpenAlexW2126274204MaRDI QIDQ3579213

No author found.

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)

Related Items (14)

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

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