We show that there are CNF formulas which can be refuted in resolution
in both small space and small width, but for which any small-width
proof must have space exceeding by far the linear worst-case upper
bound. This significantly strengthens the space-width trade-offs in
[Ben-Sasson '09]}, and provides one more ... more >>>

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.
Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ... more >>>