Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BLOCK SENITIVITY:
Reports tagged with block senitivity:
TR22-019 | 17th February 2022
Guangxu Yang, Jiapeng Zhang

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). ... more >>>




ISSN 1433-8092 | Imprint