Lifting Theorems Meet Information Complexity: Known and New Lower Bounds of Set-disjointness

Guangxu Yang, Jiapeng Zhang

Set-disjointness problems are one of the most fundamental problems in communication complexity and have been extensively studied in past decades. Given its importance, many lower b…