Pseudo-deterministic proofs
From MaRDI portal
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Abstract: We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier. Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one.
Recommendations
Cites work
- A note on the graph isomorphism counting problem
- Competing provers yield improved Karp-Lipton collapse results
- Complexity Measures for Public-Key Cryptosystems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Constant-round interactive proofs for delegating computation
- Construction of defining relators for finite groups
- Hardness vs randomness
- scientific article; zbMATH DE number 1405686 (Why is no real title available?)
- IP = PSPACE
- Lattice problems in NP ∩ coNP
- Modern cryptography, probabilistic proofs and pseudo-randomness
- Nondeterministic Space is Closed under Complementation
- On the possibilities and limitations of pseudodeterministic algorithms
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Pseudodeterministic constructions in subexponential time
- Search versus decision for election manipulation problems
- The method of forced enumeration for nondeterministic automata
Cited in
(9)- Deterministic FOIES are strictly weaker
- On the possibilities and limitations of pseudodeterministic algorithms
- Brief announcement: Zero-knowledge protocols for search problems
- scientific article; zbMATH DE number 7378343 (Why is no real title available?)
- Planar Maximum Matching: Towards a Parallel Algorithm
- scientific article; zbMATH DE number 2236687 (Why is no real title available?)
- A map of witness maps: new definitions and connections
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- Polynomial-time pseudodeterministic construction of primes
This page was built for publication: Pseudo-deterministic proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993280)
