Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with direct sum problems:
TR08-096 | 8th September 2008
Andrew Drucker

Multitask Efficiencies in the Decision Tree Model

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

TR22-114 | 16th August 2022
Hao Wu

Direct Sum Theorems From Fortification

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