Quantum multiparty communication complexity and circuit lower bounds

DOI10.1017/S0960129508007263MaRDI QIDQ3616221zbMATH OpenFDO

Authors Iordanis Kerenidis

Publication date 24 March 2009

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0960129508007263

zbMATH Keywords

simulation theorem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Recommendations

• Quantum Multiparty Communication Complexity and Circuit Lower Bounds
• scientific article; zbMATH DE number 5568623
• Multi-party Quantum Communication Complexity with Routed Messages
• Lower Bounds for Quantum Communication Complexity
• Communication Complexity of Simultaneous Messages

Cites work

• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On ACC
• On the power of small-depth threshold circuits
• Quantum computing, postselection, and probabilistic polynomial-time
• Quasi‐random classes of hypergraphs
• The BNS lower bound for multi-party protocols is nearly optimal
• The BNS-Chung criterion for multi-party communication complexity

Cited in

(15)

• Experimental multipartner quantum communication complexity employing just one qubit
• Multiparty communication complexity and threshold circuit size of AC^0
• New bounds for the garden-hose model
• The garden-hose model
• Multi-party Quantum Communication Complexity with Routed Messages
• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• On the tightness of the Buhrman-Cleve-Wigderson simulation
• Quantum weakly nondeterministic communication complexity
• scientific article; zbMATH DE number 6851887 (Why is no real title available?)
• Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication
• A Quantum Multiparty Packing Lemma and the Relay Channel
• The garden hose complexity for the equality function
• A Communication-Efficient Nonlocal Measurement With Application to Communication Complexity and Bipartite Gate Capacities
• Quantum Multiparty Communication Complexity and Circuit Lower Bounds
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Quantum multiparty communication complexity and circuit lower bounds

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