Reconstructing Algebraic Functions from Mixed Data

DOI10.1137/S0097539796297577zbMath0915.68088OpenAlexW2101610102MaRDI QIDQ4210162

Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Sigal Ar

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796297577

zbMATH Keywords

multivariate polynomialsPAC learningerror correcting codespolynomial factoringpolynomial interpolationBezout's theoremnoisy interpolation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (8)

Decoding of Reed Solomon codes beyond the error-correction bound ⋮ Query complexity of membership comparable sets. ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Pseudorandom generators without the XOR lemma ⋮ Approximate evaluations of characteristic polynomials of Boolean functions ⋮ Fitting algebraic curves to noisy data ⋮ Noisy Chinese remaindering in the Lee norm ⋮ The enumerability of P collapses P to NC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on enumerative counting
• Interpolating polynomials from their values
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Occam's razor
• Factoring polynomials with rational coefficients
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Highly resilient correctors for polynomials
• Decoding of Reed Solomon codes beyond the error-correction bound
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Learning Decision Trees Using the Fourier Spectrum
• Bounded distance+1 soft-decision Reed-Solomon decoding
• Factoring Polynomials Over Large Finite Fields

This page was built for publication: Reconstructing Algebraic Functions from Mixed Data