epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials
Lists
Only you see this
Abstract
We present a simple explicit construction of a probability distribution supported on (p − 1)2 vectors in Zpn, where p ⩾ n/ϵ is a prime, for which the absolute value of each nontrivial Fourier coefficients is bounded by ϵ. This construction is used to derandomize the algorithm of Mansour (1992) that interpolates a sparse polynomial in polynomial time in the bit complexity model.
BibTeX
@article{alon1995epsilon,
author = {Noga Alon and Yishay Mansour},
title = {{epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials}},
journal = {Inf. Process. Lett.},
year = {1995},
doi = {10.1016/0020-0190(95)00032-8},
}Loading related content...