11 3 our first main contribution is to exhibit a number of nontrivial lower bounds for matrix search problems