中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
题名:
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.
语种: 英语
内容类型: 期刊论文
URI标识: http://ir.iscas.ac.cn/handle/311060/1302
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:
File Name/ File Size Content Type Version Access License
bj01130931.pdf(1396KB)----限制开放 联系获取全文

Recommended Citation:
Ron M. Roth,Gyora M. Benedek. Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$[J]. SIAM Journal on Computing,1991-01-01,20(2):291-314.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Ron M. Roth]'s Articles
[Gyora M. Benedek]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Ron M. Roth]‘s Articles
[Gyora M. Benedek]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace