Time-space tradeoffs for set operations (Q1210542)

The paper deals with \(R\)-way branching programs as well as with a more restricted model of comparison branching programs. The authors show the time-space tradeoff \(TS=\Omega(n^ 2)\) for the set complementation and \(TS-\Omega(n^{3/2})\) for the set intersection problem. Tradeoffs of such type were known before. The authors extend them for other problems including the set union, set disjointedness and set intersection problems. The lower bound argument is standard: show that for a random instances any small decision tree produces only few distinct outputs while the problem itself has many outputs. The main difficulties appear when estimating these probabilities for concrete problems.