Direct sum theorems state that the cost of solving k instances of a problem is at least \Omega(k) times
the cost of solving a single instance. We prove the first such results in the randomised parity
decision tree model. We show that a direct sum theorem holds whenever (1) the ... more >>>

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results.

\textbf{Complement:} There is a language L recognised by an n-state UFA such that the complement language \overline{L} requires NFAs with n^{\tilde{\Omega}(\log n)} states. This improves on ... more >>>

Let f: \{0,1\}^n \to \{0, 1\} be a boolean function, and let f_\land (x, y) = f(x \land y) denote the AND-function of f, where x \land y denotes bit-wise AND. We study the deterministic communication complexity of f_\land and show that, up to a \log n factor, it is ... more >>>