Quantum communication complexity of symmetric predicates

DOI10.1070/IM2003v067n01ABEH000422zbMath1088.68052arXivquant-ph/0204025OpenAlexW2053590396MaRDI QIDQ4674584

Alexander A. Razborov

Publication date: 17 May 2005

Published in: Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0204025

zbMATH Keywords

set disjointness predicate

Mathematics Subject Classification ID

Related Items (28)

A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Hellinger volume and number-on-the-forehead communication complexity ⋮ The communication complexity of the Hamming distance problem ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Unbounded-error quantum query complexity ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Algorithmic Polynomials ⋮ The NOF multiparty communication complexity of composed functions ⋮ The hardest halfspace ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Polynomial degree vs. quantum query complexity ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Exponential separation of quantum and classical online space complexity ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Lower bounds in communication complexity based on factorization norms ⋮ Unnamed Item ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ The complexity of quantum disjointness ⋮ Quantum communication and complexity. ⋮ Unnamed Item ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: Quantum communication complexity of symmetric predicates