A ZPP NP[1] Lifting Theorem

DOI10.1145/3428673zbMath1495.68091OpenAlexW3098948044MaRDI QIDQ5862289

No author found.

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

communication complexityquery complexity

Mathematics Subject Classification ID

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

Related Items (2)

Amplification with one \textsf{NP} oracle query ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity

This page was built for publication: A ZPP ^NP[1] Lifting Theorem