Pseudodeterministic constructions in subexponential time

DOI10.1145/3055399.3055500zbMath1370.68326arXiv1612.01817OpenAlexW2574746104MaRDI QIDQ4978012

Rahul Santhanam, Igor C. Oliveira

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

explicit constructionsderandomizationprime numberspseudorandomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Primes (11A41)

Related Items (7)

Pseudo-deterministic Proofs ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle

This page was built for publication: Pseudodeterministic constructions in subexponential time