Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.


翻译:已知的多元性乘数在密度大和稀少的情况下都具有准线性复杂性。 但对于这个问题,并没有给出真正的线性算法, 也没有给出真正的线性算法, 也不清楚它是否可能存在。 这为更简单的核查多元性产品问题提供了一个更好的算法空间。 虽然发现确定性方法似乎遥不可及, 但对于在代数操作数量上是最佳的问题, 存在着概率性算法。 我们研究这一问题的概括性, 以核查多元性产品模擬为稀薄的稀薄的稀释器。 我们调查了它对于稠密和稀散的多种复制品的微复杂性。 特别是, 当divisor 具有恒定的常温度和第二高度单度单项性时, 我们能够显示核查比模块化倍增倍增的优先性。 我们使用这些结果来获得关于标准多元性倍增倍增性核查的微复杂性的新界限。 特别是, 我们通过改进Kaminski 的结果和开发第一个准性微数项产品核查的准性多元性算法, 在密度大的情况下, 提供比复杂性模型模型的最佳算法。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
最新《Transformers模型》教程,64页ppt
专知会员服务
306+阅读 · 2020年11月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年3月4日
Arxiv
0+阅读 · 2021年3月4日
A Spectral Approach to Polytope Diameter
Arxiv
0+阅读 · 2021年3月3日
Arxiv
0+阅读 · 2021年3月3日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
最新《Transformers模型》教程,64页ppt
专知会员服务
306+阅读 · 2020年11月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员