In this paper we study program checking (in the
sense of Blum and Kannan) using constant-depth circuits as
checkers. Our focus is on the number of queries made by the
checker to the program being checked and we term this as the
query complexity of the checker for the given problem. We
study the query complexity of both deterministic and
randomized constan-depth circuits as checkers. We show
sub-linear lower bounds on the query complexity of checkers
that are deterministic constant-depth circuits for Parity
and certain P-complete and NC^1-complete problems. On the
other hand, we show that there are randomized constant-depth
circuits of constant query complexity that check Parity and
suitably encoded complete problems for P, NL, and NC^1. The
latter results are proved using techniques from the
PCP(poly,1) protocol for 3-SAT.