【24h】

Improved Polynomial Identity Testing for Read-Once Formulas

机译:改进的一次性公式多项式身份测试

获取原文
获取原文并翻译 | 示例

摘要

An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are {+, ×} and such that every input variable labels at most one leaf. In this paper we study the problems of giving deterministic identity testing and reconstruction algorithms for ROFs. Our main result is an n~(O(k+log n)) time deterministic algorithm for checking whether a black box holding the sum of k n-variate ROFs computes the zero polynomial. In other words, we provide a hitting set of size n~(O(k+log n)) for the sum of k ROFs. This result greatly improves [27] where an n~(O(k~2+n~(1/2))) algorithm was given for the problem.rnUsing our new results we obtain a deterministic reconstruction algorithms for read-once formulas that runs in time n~(O(log n)).rnIn fact, our results also hold for the more general model of preprocessed read-once formulas that we define in this paper. In this model we are allowed to replace each variable x_i with a polynomial T_i(x_i).rnOur techniques are very close to the techniques in [27]. The main difference is that we obtain several tighter versions of the tools first used there. In particular we obtain a better version of the hardness of representation approach which was first used in [27]. This technique can be thought of as a very explicit way of transforming (mild) hardness of a very structured polynomial to an identity testing algorithm.
机译:算术一次读取公式(简称ROF)是一种公式(其基础图为树的电路),其中的运算为{+,×},并且每个输入变量最多标记一个叶子。在本文中,我们研究了为ROF提供确定性身份测试和重构算法的问题。我们的主要结果是一种n〜(O(k + log n))时间确定性算法,用于检查持有k个n变量ROF的总和的黑盒是否计算零多项式。换句话说,我们为k个ROF的总和提供了大小为n〜(O(k + log n))的匹配集。该结果大大改善了[27],其中针对该问题给出了n〜(O(k〜2 + n〜(1/2)))算法。使用我们的新结果,我们获得了一次确定公式的确定性重构算法,该公式可用于以下操作:运行时间为n〜(O(log n))。实际上,我们的结果也适用于本文中定义的更通用的预处理一次读取公式模型。在该模型中,我们允许将每个变量x_i替换为多项式T_i(x_i)。rn我们的技术与[27]中的技术非常接近。主要区别在于,我们获得了最初在此处使用的工具的几种更严格的版本。特别是,我们获得了表示方法硬度的更好版本,该方法首先在[27]中使用。可以将此技术视为将非常结构化的多项式的(中等)硬度转换为身份测试算法的一种非常明确的方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号