{'fraction_non_alphanumeric': 0.034532374100719423, 'fraction_numerical': 0.0057553956834532375, 'mean_word_length': 4.919148936170213, '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}}
Simulation Methods in Communication Lower Bounds, Revisited

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). This simulation provides a systematic way to convert a communication protocol into a corresponding decision tree. Though it is very convenient in many applications, there are still some challenges in this framework. A major problem is that Raz-McKenize simulation requires a very large gadget. In this paper, we revise Raz-McKenzie simulation. We introduce a white-box simulation, proving lifting theorems for block sensitivity with constant-size gadgets. Concretely, we show there is a constant-size gadget g such that for any Boolean function f , the corruption bound of f ◦ g is lower bounded by Ω(bs(f)). Combined with a result of Beame et al. (CCC 2005), this implies the randomized communication complexity of f ◦ g is lower bounded by Ω(bs(f)). Besides the result itself, we believe our simulation technique may have more applications in diverse areas. We also discuss why our simulation method has a potential to avoid the large-size gadget bottleneck in Raz-McKenzie simulation.