Lossless Hardness Condensation in Deterministic Communication ComplexityResearch Paper
In two-party communication complexity, Alice holds a row , Bob holds a column , and they must compute a Boolean entry by exchanging bits. The input sets can be far larger than the cost: a problem of cost may have inputs of length much more than . A basic structural question is whether the difficulty of a problem is already visible on a…