A ZPP^NP[1] lifting theorem

DOI10.1145/3428673zbMATH Open1495.68091OpenAlexW3098948044MaRDI QIDQ5862289FDOQ5862289

Authors:

Publication date: 7 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

Recommendations

• On zero error algorithms having oracle access to one query
• Computing and Combinatorics
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• The 1-versus-2 queries problem revisited

zbMATH Keywords

query complexitycommunication complexity

Mathematics Subject Classification ID

Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Communication complexity, information complexity (68Q11)

Cited In (9)

• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Amplification with one \textsf{NP} oracle query
• The landscape of communication complexity classes
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• The landscape of communication complexity classes
• On zero error algorithms having oracle access to one query
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Query-to-communication lifting for BPP using inner product

This page was built for publication: A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem

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