We consider deterministic and randomized AC0 program checkers for standard P-complete and NC1-complete problems. Our focus is on the query complexity of the checker: i.e. the number of queries made by the checker to the program. We show that OMEGA(n^{1-\epsilon is a lower bound on the query complexity of deterministic AC0 checkers for these problems, for each epsilon>0, and inputs of length n. On the other hand, we design randomized AC0 checkers of constant query complexity for these problems.