In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e., a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type $\mathsf{A}$. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.

More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are evasive, i.e., have decision tree complexity $\binom{n}{2}$, where $n$ is the number of vertices. It was proved in 1984 by Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297--306] if $n$ is a prime power by a topological approach. Using their method, we prove a lower bound of $\frac{1}{3}n^2-o(n^2)$ for general $n$.