Learning Polynomials with Queries: The Highly Noisy Case
From MaRDI portal
Publication:2706184
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
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
