Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$ | |
Ron M. Roth ; Gyora M. Benedek | |
刊名 | SIAM Journal on Computing |
1991 | |
卷号 | 20期号:2页码:291-314 |
合作状况 | 其它 |
英文摘要 | A function $f:\{ 0,1\} ^n \to \{ 0,1\} $ is called $t$-sparse if the $n$-variable polynomial representation of $f$ over $GF(2)$ contains at most $t$ monomials. Such functions are uniquely determined by their values at the so-called critical set of all binary $n$-tuples of Hamming weight $ \geqq n - \lfloor \log _2 t \rfloor - 1$. An algorithm is presented for interpolating any $t$-sparse function $f$, given the values of $f$ at the critical set. The time complexity of the proposed algorithm is proportional to $n$, $t$, and the size of the critical set. Then, the more general problem of approximating 1-sparse functions is considered, in which case the approximating function may differ from $f$ at a fraction $\varepsilon $ of the space $\{ 0,1\} ^n $. It is shown that $O(({t / \varepsilon }) \cdot n)$ evaluation points are sufficient for the (deterministic) $\varepsilon $-approximation of any $t$-sparse function, and that an order $(t / \varepsilon )^{\alpha (t,\varepsilon )} \cdot \log n$ points are necessary for this purpose, where $\alpha (t,\varepsilon ) \geqq 0.694$ for a large range of $t$ and $\varepsilon $. Similar bounds hold for the $t$-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the $\varepsilon $-approximation of any $t$-sparse function. |
收录类别 | 其他 |
语种 | 英语 |
公开日期 | 2010-05-13 |
内容类型 | 期刊论文 |
源URL | [http://124.16.136.157/handle/311060/1302] |
专题 | 软件研究所_软件所图书馆_期刊论文 |
推荐引用方式 GB/T 7714 | Ron M. Roth,Gyora M. Benedek. Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$[J]. SIAM Journal on Computing,1991,20(2):291-314. |
APA | Ron M. Roth,&Gyora M. Benedek.(1991).Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$.SIAM Journal on Computing,20(2),291-314. |
MLA | Ron M. Roth,et al."Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$".SIAM Journal on Computing 20.2(1991):291-314. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论