Article ID Journal Published Year Pages File Type
6872369 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract
This gives new results on two problems related to communication complexity. Namely, (i) a new separation between the size of a fooling set and the rank of a 0/1-matrix, and (ii) an improved lower bound on the nondeterministic communication complexity of the clique vs. independent set problem are given.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Some improved bounds on communication complexity via new decomposition of cliques
Authors
,