Unexpected upper bounds on the complexity of some communication games

DOI10.1007/3-540-58201-0_53zbMath1422.68134OpenAlexW1534236576MaRDI QIDQ4632411

Pavel Pudlák

Publication date: 29 April 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58201-0_53

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80)

Related Items (1)

Hadamard tensors and lower bounds on multiparty communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of small-depth threshold circuits
• Lower bounds to the complexity of symmetric Boolean functions
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The BNS lower bound for multi-party protocols is nearly optimal
• Rounds in Communication Complexity Revisited
• On sets of integers containing k elements in arithmetic progression
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Quasi-random graphs

This page was built for publication: Unexpected upper bounds on the complexity of some communication games