Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.
This relies on a novel technique ... more >>>

Q-resolution and its variations provide the underlying proof
systems for the DPLL-based QBF solvers. While (long-distance) Q-resolution
models a conflict driven clause learning (CDCL) QBF solver, it is not
known whether the inverse is also true. This paper provides a negative
answer to this question. This contrasts with SAT solving, ... more >>>

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>