Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FORTIFICATION:
Reports tagged with fortification:
TR22-114 | 16th August 2022
Hao Wu

Direct Sum Theorems From Fortification

Revisions: 1

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles can be ... more >>>




ISSN 1433-8092 | Imprint