Loading...
Please wait, while we are loading the content...
Similar Documents
Approximate Checking of Polynomials and Functional Equations
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kumar, S. Ravi Rubinfeld, Ronitt |
| Copyright Year | 1996 |
| Abstract | In this paper, we show how to check programs that compute polynomials and functions deened by addition theorems | in the realistic setting where the output of the program is approximate instead of exact. We present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the aarmative a question raised by GLR + 91, RS92, RS96]. We obtain this by rst building approximate self-testers for linear and multilinear functions. We then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by Rub94]. In both cases, we show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, we explore the use of reductions between functional equations in the context of approximate self-testing. Our results have implications for the stability theory of functional equations. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~iliano/muri/reports/97-98/funda1.ps |
| Alternate Webpage(s) | http://www.cs.cornell.edu/Info/People/ronitt/PAP/approx.ps |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation algorithm Checking (action) GLR parser Polynomial ring Robustness (computer science) Self-replication |
| Content Type | Text |
| Resource Type | Article |
