{'fraction_non_alphanumeric': 0.045993031358885016, 'fraction_numerical': 0.010452961672473868, 'mean_word_length': 4.698412698412699, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
There are no zero-hard problems in multiparty communication complexity

We study the feasibility of generalizing the notions of completeness and hardness in 2-party communication complexity (Babai, Frankl, Simon, FOCS 1986) to the “number-on-forehead” (NOF) model of k-party communication complexity with k ≥ 3 (Chandra, Furst, Lipton, STOC 1983). Beame et al. (Theory of Computing, 2010) suggest that the kparty version of NP may not have any complete families under the natural (cylindrical, polynomially bounded) reductions. We confirm this in a strong sense. Let us call a family F = (fn) of k-party communication problems (one problem for every input length n) zero-hard if all families of k-party communication problems solvable with zero communication (cylinders) admit polynomially bounded reductions to F . We show that there are no zero-hard families of k-party communication problems. Furthermore, we study reduction concepts that “allow communication.” We arrive at two definitions of reductions with t bits of communication, one of Karp-style, the other of Cook-style. Let us consider the class of problems solvable with t bits of communication. We show that no problem is hard for this class with respect to t-bit Karp-style reduction and (t − 1)-bit Cook-style reduction. All the proofs are by simple counting arguments, much in the spirit of Beame et al.. The main purpose of the paper is clarification of the concepts.