Pseudo-deterministic Proofs
From MaRDI portal
Publication:4993280
DOI10.4230/LIPIcs.ITCS.2018.17zbMath1462.68049arXiv1706.04641OpenAlexW2962853121MaRDI QIDQ4993280
Dhiraj Holden, Ofer Grossman, Shafi Goldwasser
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1706.04641
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (5)
A map of witness maps: new definitions and connections ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Planar Maximum Matching: Towards a Parallel Algorithm
Cites Work
- Unnamed Item
- Construction of defining relators for finite groups
- The method of forced enumeration for nondeterministic automata
- A note on the graph isomorphism counting problem
- Modern cryptography, probabilistic proofs and pseudo-randomness
- Hardness vs randomness
- Competing provers yield improved Karp-Lipton collapse results
- Search versus Decision for Election Manipulation Problems
- On the possibilities and limitations of pseudodeterministic algorithms
- Lattice problems in NP ∩ coNP
- Complexity Measures for Public-Key Cryptosystems
- Nondeterministic Space is Closed under Complementation
- IP = PSPACE
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Pseudodeterministic constructions in subexponential time
- Constant-round interactive proofs for delegating computation
This page was built for publication: Pseudo-deterministic Proofs
