Hadamard tensors and lower bounds on multiparty communication complexity

DOI10.1007/S00037-012-0052-6zbMATH Open1286.68189OpenAlexW2027624900MaRDI QIDQ371197FDOQ371197

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/

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

zbMATH Keywords

lower boundscommunication complexitymultiparty communication

Mathematics Subject Classification ID

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

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• On Some Exponential Sums
• Communication Complexity
• Title not available (Why is that?)
• 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
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Rounds in Communication Complexity Revisited
• Multiparty Communication Complexity and Threshold Circuit Size of AC^0
• Communication Complexity and Quasi Randomness
• Lower Bounds for Quantum Communication Complexity
• The BNS-Chung criterion for multi-party communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model
• Title not available (Why is that?)
• Title not available (Why is that?)
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Quasi‐random classes of hypergraphs
• Title not available (Why is that?)
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Title not available (Why is that?)
• Unexpected upper bounds on the complexity of some communication games
• A Hadamard matrix of order 428

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)