Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author K.V. Subrahmanyam:

TR98-078 | 1st December 1998
Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

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 ... more >>>

ISSN 1433-8092 | Imprint