  Efficient distributed computing offers a scalable strategy for solving
resource-demanding tasks such as parallel computation and circuit optimisation.
Crucially, the communication overhead introduced by the allotment process
should be minimised -- a key motivation behind the communication complexity
problem (CCP). Quantum resources are well-suited to this task, offering clear
strategies that can outperform classical counterparts. Furthermore, the
connection between quantum CCPs and nonlocality provides an
information-theoretic insights into fundamental quantum mechanics. Here we
connect quantum CCPs with a generalised nonlocality framework -- beyond the
paradigmatic Bell's theorem -- by incorporating the underlying causal
structure, which governs the distributed task, into a so-called nonlocal hidden
variable model. We prove that a new class of communication complexity tasks can
be associated to Bell-like inequalities, whose violation is both necessary and
sufficient for a quantum gain. We experimentally implement a multipartite CCP
akin to the guess-your-neighbour-input scenario, and demonstrate a quantum
advantage when multipartite Greenberger-Horne-Zeilinger (GHZ) states are shared
among three users.
