Learning polynomials with queries: The highly noisy case
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 294-303
- https://doi.org/10.1109/sfcs.1995.492485
Abstract
Given a function f mappping n-variate inputs from a finite field F into F, we consider the task of reconstructing a list of all n-variate degree d polynomials which agree with f on a tiny but non-negligible fraction, /spl delta/, of the input space. We give a randomized algorithm for solving this task which accesses f as a black box and runs in time polynomial in 1//spl delta/, n and exponential in d, provided /spl delta/ is /spl Omega/(/spl radic/(d.Keywords
This publication has 28 references indexed in Scilit:
- Randomized Interpolation and Approximation of Sparse PolynomialsSIAM Journal on Computing, 1995
- Learning to model sequences generated by switching distributionsPublished by Association for Computing Machinery (ACM) ,1995
- Exact Identification of Read-Once Formulas Using Fixed Points of Amplification FunctionsSIAM Journal on Computing, 1993
- Learning fallible finite state automataPublished by Association for Computing Machinery (ACM) ,1993
- A noise model on learning sets of stringsPublished by Association for Computing Machinery (ACM) ,1992
- On learning from queries and counterexamples in the presence of noiseInformation Processing Letters, 1991
- Self-testing/correcting for polynomials and for approximate functionsPublished by Association for Computing Machinery (ACM) ,1991
- Interpolating polynomials from their valuesJournal of Symbolic Computation, 1990
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978