Hadamard tensors and lower bounds on multiparty communication complexity

DOI10.1007/S00037-012-0052-6MaRDI QIDQ371197zbMATH OpenOpenAlexFDO

Authors Jeff Ford, Anna Gál

Publication date 30 September 2013

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/607/

zbMATH Keywords

lower boundscommunication complexitymultiparty communication

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Automata, Languages and Programming
• The multiparty communication complexity of set disjointness
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The multiparty communication complexity of set disjointness
• Communication Complexity and Quasi Randomness

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3570471 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1775457 (Why is no real title available?)
• A Hadamard matrix of order 428
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Communication Complexity
• Communication Complexity and Quasi Randomness
• Disjointness is hard in the multiparty number-on-the-forehead model
• Lower Bounds for Quantum Communication Complexity
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• On ACC
• On Some Exponential Sums
• On the power of small-depth threshold circuits
• Quasi‐random classes of hypergraphs
• Rounds in Communication Complexity Revisited
• The BNS lower bound for multi-party protocols is nearly optimal
• The BNS-Chung criterion for multi-party communication complexity
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Unexpected upper bounds on the complexity of some communication games

Cited in

(1)

• Automata, Languages and Programming

This page was built for publication: Hadamard tensors and lower bounds on multiparty communication complexity

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