We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

We develop a paradigm for studying multi-player deterministic communication,
based on a novel combinatorial concept that we call a {\em strong fooling
set}. Our paradigm leads to optimal lower bounds on the per-player
communication required for solving multi-player $\textsc{equality}$
problems in a private-message setting. This in turn gives a ... more >>>

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>