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

Full work available at URL https://doi.org/10.1007/S00037-025-00266-7

zbMATH Keywords

Boolean functionsdecision treespseudo-determinismrandomnesssearch problems

Mathematics Subject Classification ID

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

Cites work

• A characterization of tree-like resolution size
• Boolean function complexity. Advances and frontiers.
• Complexity measures and decision tree complexity: a survey.
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Log-rank and lifting for AND-functions
• Many hard examples for resolution
• Monotone circuit lower bounds from resolution
• Near optimal seperation of tree-like and general resolution
• On the pseudo-deterministic query complexity of NP search problems
• Private vs. common random bits in communication complexity
• Randomized versus deterministic decision tree size
• Search Problems in the Decision Tree Model
• Short proofs are narrow—resolution made simple
• Space complexity of random formulae in resolution
• The efficiency of resolution and Davis-Putnam procedures
• Tseitin's tautologies and lower bounds for Nullstellensatz proofs

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)