On the possibilities and limitations of pseudodeterministic algorithms

DOI10.1145/2422436.2422453MaRDI QIDQ2986864zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Dana Ron, Shafi Goldwasser

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2422436.2422453

zbMATH Keywords

BPPsearch problemssublinear-time computationsunique solutionsZPP

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Recommendations

• Pseudodeterministic algorithms and the structure of probabilistic time
• On Pseudodeterministic Approximation Algorithms.
• Pseudodeterministic constructions in subexponential time
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• scientific article; zbMATH DE number 1332665
• Pseudodeterminism: promises and lowerbounds
• Some algorithmic problems for pseudovarieties
• Pseudo-deterministic proofs
• On the pseudo-deterministic query complexity of NP search problems
• Probabilistically checkable proofs and their consequences for approximation algorithms

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(14)

• An algorithmic view of pseudochaos
• From determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace (Invited Talk)
• Pseudodeterministic constructions in subexponential time
• Pseudo-deterministic proofs
• Brief announcement: Zero-knowledge protocols for search problems
• On Pseudodeterministic Approximation Algorithms.
• Pseudo-derandomizing learning and approximation
• Planar Maximum Matching: Towards a Parallel Algorithm
• Pseudodeterministic algorithms and the structure of probabilistic time
• Multi-pseudodeterministic algorithms
• Total NP search problems with abundant solutions
• Unambiguous parity-query complexity
• Complete problems for multi-pseudodeterministic computations
• Polynomial-time pseudodeterministic construction of primes

This page was built for publication: On the possibilities and limitations of pseudodeterministic algorithms

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