Testing Multivariate Linear Functions:Overcoming the GeneratorBottleneck

Abstract

The problem of testing program correctness has received considerable attention in computer science. One approach to this problem is the notion of self-testing programs \cite{BlumLubyRubinfeld}. Self-testing usually becomes more costly in the case of testing multivariate functions. In this paper we present efficient methods for self-testing multivariate linear functions. We then apply these methods to several multivariate linear problems to construct efficient self-testers.