A comparison of two lower-bound methods for communication complexity
From MaRDI portal
Publication:1350995
DOI10.1016/S0304-3975(96)00062-XzbMath0874.68150OpenAlexW1580860198MaRDI QIDQ1350995
Juraj Hromkovič, Georg Schnitger, Martin Dietzfelbinger
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00062-x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)
Related Items (18)
The rectangle covering number of random Boolean matrices ⋮ The corruption bound, log-rank, and communication complexity ⋮ Communication Complexity and Lower Bounds on Multilective Computations ⋮ Some improved bounds on communication complexity via new decomposition of cliques ⋮ The (minimum) rank of typical fooling-set matrices ⋮ The augmentation property of binary matrices for the binary and Boolean rank ⋮ Around the log-rank conjecture ⋮ Bipartite perfect matching as a real polynomial ⋮ Probabilism versus Alternation for Automata ⋮ On the complexity of Boolean matrix ranks ⋮ Fooling sets and the spanning tree polytope ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ Partition arguments in multiparty communication complexity ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Ordered biclique partitions and communication complexity problems ⋮ Fooling-sets and rank
Cites Work
This page was built for publication: A comparison of two lower-bound methods for communication complexity
