Chicago Journal of Theoretical Computer Science

Volume 2002

Article 2

Published by Dept. CS U. Chicago. Copyright 2002 CJTCS

The Query Complexity of Program Checking by Constant-Depth Circuits

V. Arvind and K. V. Subrahmanyam (Chennai, India) and N. V. Vinodchandran (Lincoln, Nebraska)
5 December 2002

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.

DOI: 10.4086/cjtcs.2002.002
[] [] Article 2
[back] Volume 2002 [back] Published articles
[CJCTS home]