Multi-pseudodeterministic algorithms

DOI10.1007/978-3-031-88946-2_2MaRDI QIDQ6877286zbMATH OpenFDO

Authors Oded Goldreich

Publication date 8 January 2026

Full work available at URL https://doi.org/10.1007/978-3-031-88946-2_2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Cites work

• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Bipartite perfect matching in pseudo-deterministic NC
• Computational Complexity
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• On defining PPT-search problems
• On the possibilities and limitations of pseudodeterministic algorithms
• Reproducibility and pseudo-determinism in log-space

Cited in

(1)

• Polynomial-time pseudodeterministic construction of primes

This page was built for publication: Multi-pseudodeterministic algorithms

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