Complete problems for multi-pseudodeterministic computations

DOI10.4230/LIPICS.ITCS.2021.66MaRDI QIDQ7229355zbMATH OpenFDO

Authors Peter B. Dixon, Aduri Pavan, N. V. Vinodchandran

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.66

zbMATH Keywords

circuit acceptancecollision probabilitycompletenessentropy approximationpseudodeterminism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bipartite perfect matching in pseudo-deterministic NC
• Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• On Pseudodeterministic Approximation Algorithms.
• On the possibilities and limitations of pseudodeterministic algorithms
• Pseudo-derandomizing learning and approximation
• Pseudo-Deterministic Streaming.
• Pseudodeterministic constructions in subexponential time
• Reproducibility and pseudo-determinism in log-space

Cited in

(1)

• Polynomial-time pseudodeterministic construction of primes

This page was built for publication: Complete problems for multi-pseudodeterministic computations

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