A ZPP^NP[1] lifting theorem

DOI10.1145/3428673MaRDI QIDQ5862289zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(9)

• Query-to-communication lifting for BPP using inner product
• 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

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)