A Matching Vector (\mathbf{MV}) family modulo a positive integer m \ge 2 is a pair of ordered lists \mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K) and \mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K) where \mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n with the following property: for any i \in [K], the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit C : \{0,1\}^n \to \{0,1\}^{n+1}, and the goal is to find a y \in \{0,1\}^{n+1} that is not in the image of C. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit C\colon\{0,1\}^n\to\{0,1\}^m, m>n, the task is to find a y\in\{0,1\}^m outside the range of C. For an integer k\geq 2, NC^0_k-AVOID is a special case of AVOID where each output bit of C depends on at most k ... more >>>