Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-078 | 1st December 1998 00:00

The Query Complexity of Program Checking by Constant-Depth Circuits



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.

ISSN 1433-8092 | Imprint