On promise problems: a survey

DOI10.1007/11685654_12MaRDI QIDQ7010306zbMATH OpenFDO

Authors Oded Goldreich

Publication date 19 March 2025

Full work available at URL https://doi.org/10.1007/11685654_12

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Cited in

(12)

• The adversarial Stackelberg value in quantitative games
• Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
• Communication complexity vs randomness complexity in interactive proofs
• Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
• Flexible constraint satisfiability and a problem in semigroup theory
• Distributed generalized Deutsch-Jozsa algorithm
• Bounded-memory strategies in partial-information games
• Sensitivity of symmetric Boolean functions
• Algorithms for identifying flagged and guarded linear systems
• Software testing in computable analysis
• Quantum polynomial hierarchies: Karp-Lipton, error reduction, and lower bounds
• Minimum clique bicoloring

This page was built for publication: On promise problems: a survey

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