Communication complexities of symmetric XOR functions

MaRDI QIDQ3636247zbMATH OpenFDO

Authors Yaoyun Shi, Zhi-Qiang Zhang

Publication date 30 June 2009

zbMATH Keywords

communication complexityquantum communicationXOR functions

Mathematics Subject Classification ID

Quantum computation (81P68) Communication theory (94A05)

Recommendations

• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
• The unbounded-error communication complexity of symmetric functions
• Structure of protocols for XOR functions
• Efficient quantum protocols for XOR functions
• Quantum communication complexity of symmetric predicates

Cited in

(16)

• The unbounded-error communication complexity of symmetric functions
• Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
• Communication complexity of permutation-invariant functions
• Structure of protocols for XOR functions
• The NOF multiparty communication complexity of composed functions
• A short list of equalities induces large sign-rank
• A lifting theorem with applications to symmetric functions
• Efficient quantum protocols for XOR functions
• Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
• One-way communication complexity of symmetric Boolean functions.
• Bounds on oblivious multiparty quantum communication complexity
• Quantum and classical communication complexity of permutation-invariant functions
• On the parity complexity measures of Boolean functions

This page was built for publication: Communication complexities of symmetric XOR functions

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