We present methods for computing the distance from a Boolean polynomial on $m$ variables of degree $m-3$ (i.e., a member of the Reed-Muller code $RM(m-3,m)$) to the space of lower-degree polynomials ($RM(m-4,m)$). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of $RM(4,8)$ in $RM(5,8)$ is 26 and the covering radius of $RM(5,9)$ in $RM(6,9)$ is between 28 and 32 inclusive, and we get improved lower bounds for higher~$m$. We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to $RM(m-4,m)$.


翻译:我们提出了从布林多球体距离计算方法,其变量为m-3美元(即Reed-Muller代码的一名成员RM(m-3,m)美元)至较低度多球体空间(RM(m-4,m)美元)的距离计算方法。这些方法对多球体的代表性清单适用这些方法,表明以5,8美元计的RM(4,8)美元半径为26美元,以6,9美元计的RM(5,9美元)半径在28至32美元之间,我们得到了更高度多球体空间(m)(m-3,m)的更低界限。我们还对文献中各种多球体界应用了我们的方法,从而改进了从2个恢复性多球体到$RM(m,m,4,m)美元的已知距离界限。

0
下载
关闭预览

相关内容

深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
已删除
将门创投
5+阅读 · 2018年11月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Arxiv
0+阅读 · 2021年8月28日
Arxiv
0+阅读 · 2021年8月28日
Arxiv
0+阅读 · 2021年8月27日
Arxiv
4+阅读 · 2019年1月14日
VIP会员
相关主题
相关VIP内容
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
已删除
将门创投
5+阅读 · 2018年11月27日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Top
微信扫码咨询专知VIP会员