Learning Polynomials with Queries: The Highly Noisy Case

DOI10.1137/S0895480198344540zbMath0968.68063OpenAlexW2157915592MaRDI QIDQ2706184

Oded Goldreich, Madhu Sudan, Ronitt Rubinfeld

Publication date: 19 March 2001

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

multivariate polynomialserror-correcting codesnoisy reconstruction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (16)

Can we locally compute sparse connected subgraphs? ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ Attacks on statistical databases: the highly noisy case ⋮ Erasures versus errors in local decoding and property testing ⋮ Collision-resistance from multi-collision-resistance ⋮ Secure PRNGs from Specialized Polynomial Maps over Any $\mathbb{F}_{q}$ ⋮ List decoding of the first-order binary Reed-Muller codes ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Three XOR-Lemmas — An Exposition ⋮ Computational Randomness from Generalized Hardcore Sets ⋮ Improvements on the Johnson bound for Reed-Solomon codes ⋮ Public-Key Encryption Schemes with Auxiliary Inputs ⋮ Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting ⋮ Unnamed Item

This page was built for publication: Learning Polynomials with Queries: The Highly Noisy Case