Quantum versus randomized communication complexity, with efficient players

DOI10.4230/LIPICS.ITCS.2021.54MaRDI QIDQ7229343zbMATH OpenFDO

Authors Uma Girish, Ran Raz, Avishay Tal

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.54

zbMATH Keywords

complexitycommunicationquantumrandomizedexponential separationforrelation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Analysis of Boolean Functions
• BQP and the polynomial hierarchy
• Entangled simultaneity versus classical interactivity in communication complexity
• Exponential separation of quantum and classical communication complexity
• Exponential separation of quantum and classical one-way communication complexity
• Forrelation: a problem that optimally separates quantum from classical computing
• Fourier analysis for probabilistic communication complexity
• Oracle separation of BQP and PH
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Quantum one-way communication can be exponentially stronger than classical communication
• Query-to-communication lifting for BPP
• Query-to-communication lifting for BPP using inner product
• Structure of protocols for XOR functions

This page was built for publication: Quantum versus randomized communication complexity, with efficient players

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