Reconstructing algebraic functions from mixed data
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 28 (2) , 503-512
- https://doi.org/10.1109/sfcs.1992.267801
Abstract
The authors consider the task of reconstructing algebraic functions given by black boxes. Unlike traditional settings, they are interested in black boxes which represent several algebraic functions-f/sub 1/, . . ., f/sub k/, where at each input x, the box arbitarrily chooses a subset of f/sub 1/(x), . . ., f/sub k/(x) to output. They show how to reconstruct the functions f/sub 1/,. . ., f/sub k/ from the black box. This allows them to group the same points into sets, such that for each set, all outputs to points in the set are from the same algebraic function. The methods are robust in the presence of errors in the black box. The model and techniques can be applied in the areas of computer vision, machine learning, curve fitting and polynomial approximation, self-correcting programs and bivariate polynomial factorization.Keywords
This publication has 16 references indexed in Scilit:
- Highly resilient correctors for polynomialsInformation Processing Letters, 1992
- Learning switching conceptsPublished by Association for Computing Machinery (ACM) ,1992
- Self-testing/correcting for polynomials and for approximate functionsPublished by Association for Computing Machinery (ACM) ,1991
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite FieldsSIAM Journal on Computing, 1990
- Interpolating polynomials from their valuesJournal of Symbolic Computation, 1990
- A deterministic algorithm for sparse multivariate polynomial interpolationPublished by Association for Computing Machinery (ACM) ,1988
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Factorization of polynomials over a finite field and the solution of systems of algebraic equationsJournal of Mathematical Sciences, 1986
- A polynomial-time reduction from bivariate to univariate integral polynomial factorizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970