Pseudo-deterministic query complexity of search problems

DOI10.1007/S00037-025-00266-7MaRDI QIDQ6892811zbMATH OpenFDO

Authors Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

Publication date 28 November 2025

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

zbMATH Keywords

decision treesBoolean functionsrandomnesssearch problemspseudo-determinism

Mathematics Subject Classification ID

Randomized algorithms (68W20) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

This page was built for publication: Pseudo-deterministic query complexity of search problems

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