Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models

DOI10.1007/978-3-642-20877-5_39zbMath1331.68078arXiv1101.4555OpenAlexW1623918381MaRDI QIDQ3010420

No author found.

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.4555

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Cryptography (94A60) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (2)

Approximate F_2-Sketching of Valuation Functions ⋮ Fourier Sparsity of GF(2) Polynomials

Cites Work

• Unnamed Item
• The communication complexity of the Hamming distance problem
• Private vs. common random bits in communication complexity
• Lower Bounds in Communication Complexity
• On the power of quantum fingerprinting
• Composition Theorems in Communication Complexity
• Communication Complexity

This page was built for publication: Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models