Abstract:
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.