Fault-tolerance and complexity (Extended abstract)
From MaRDI portal
Publication:4630260
DOI10.1007/3-540-56939-1_72zbMath1418.68075OpenAlexW2099969036MaRDI QIDQ4630260
Publication date: 29 March 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-56939-1_72
Related Items
Revisiting a result of Ko ⋮ On helping by parity-like languages ⋮ Universally serializable computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Robust machines accept easy sets
- BPP and the polynomial hierarchy
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- Robust algorithms: a different approach to oracles
- On hardness of one-way functions
- On helping by robust oracle machines
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Complexity classes without machines: on complete languages for UP
- Probabilistic quantifiers and games
- Some observations on the probabilistic algorithms and NP-hard problems
- Reductions on NP and p-selective sets
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Using inductive counting to simulate nondeterministic computation
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Sperner's lemma and robust machines
- Gap-definable counting classes
- On the power of multi-prover interactive protocols
- Classes of bounded nondeterminism
- On intractability of the classUP
- Sparse Sets, Lowness and Highness
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Relativized Questions Involving Probabilistic Algorithms
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computational Complexity of Probabilistic Turing Machines
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Lower bounds for the low hierarchy
- P-Printable Sets
- A refinement of the low and high hierarchies
- Promise problems and access to unambiguous computation
