We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.

more >>>