TY - JOUR
T1 - ϵ-discrepancy sets and their application for interpolation of sparse polynomials
AU - Alon, Noga
AU - Mansour, Yishay
N1 - Funding Information:
* Corresponding author. ’ Research supported in part by a USAV-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences. ’ Research supported in part by a grant of the Israeli Ministry of Science and Technology and by The Israel Science Foundation administered by The Israel Academy of Science and Humanities.
PY - 1995/6/23
Y1 - 1995/6/23
N2 - We present a simple explicit construction of a probability distribution supported on (p - 1)2 vectors in Zpn, where p ≥ n/ε{lunate} is a prime, for which the absolute value of each nontrivial Fourier coefficients is bounded by ε{lunate}. This construction is used to derandomize the algorithm of Mansour (1992) that interpolates a sparse polynomial in polynomial time in the bit complexity model.
AB - We present a simple explicit construction of a probability distribution supported on (p - 1)2 vectors in Zpn, where p ≥ n/ε{lunate} is a prime, for which the absolute value of each nontrivial Fourier coefficients is bounded by ε{lunate}. This construction is used to derandomize the algorithm of Mansour (1992) that interpolates a sparse polynomial in polynomial time in the bit complexity model.
KW - Analysis of algorithms
KW - Probability analysis
KW - Sparse polynomials
UR - http://www.scopus.com/inward/record.url?scp=0029326046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029326046&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(95)00032-8
DO - 10.1016/0020-0190(95)00032-8
M3 - Article
AN - SCOPUS:0029326046
SN - 0020-0190
VL - 54
SP - 337
EP - 342
JO - Information Processing Letters
JF - Information Processing Letters
IS - 6
ER -