The query complexity of program checking by constant-depth circuits

DOI10.1007/3-540-46632-0_13MaRDI QIDQ4511221zbMATH OpenFDO

Authors Vikraman Arvind, K. V. Subrahmanyam, N. V. Vinodchandran

Publication date 30 October 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46632-0_13

zbMATH Keywords

\(\text{AC}^0\) checkersprogram result checking

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1919505
• Designing programs that check their work
• Small PCPs with low query complexity
• scientific article; zbMATH DE number 4195192
• Query efficient PCPs with perfect completeness

Cited in

(2)

• Effect of look-ahead depth in evolutionary checkers
• scientific article; zbMATH DE number 1919505 (Why is no real title available?)

This page was built for publication: The query complexity of program checking by constant-depth circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511221)