Hadamard tensors and lower bounds on multiparty communication complexity

DOI10.1007/S00037-012-0052-6zbMath1286.68189OpenAlexW2027624900MaRDI QIDQ371197

Anna Gál, Jeff Ford

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjointness is hard in the multiparty number-on-the-forehead model
• On the power of small-depth threshold circuits
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The BNS lower bound for multi-party protocols is nearly optimal
• On ACC
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Quasi‐random classes of hypergraphs
• Rounds in Communication Complexity Revisited
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Unexpected upper bounds on the complexity of some communication games
• Communication Complexity
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• Communication Complexity and Quasi Randomness
• Lower Bounds for Quantum Communication Complexity
• A Hadamard matrix of order 428
• On Some Exponential Sums
• The BNS-Chung criterion for multi-party communication complexity

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