• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >A promenade through correct test sequences Ⅰ: Degree of constructible sets, Bezout's Inequality and density
【24h】

A promenade through correct test sequences Ⅰ: Degree of constructible sets, Bezout's Inequality and density

机译：A promenade through correct test sequences Ⅰ: Degree of constructible sets, Bezout's Inequality and density

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相关主题

摘要

The notion of correct test sequence was introduced in [27]. It has been widely used to design probabilistic algorithms for Polynomial Identity Testing (PIT). In this manuscript we study foundations and generalizations of this notion. We show that correct test sequences are almost omnipresent in the mathematical literature: As hitting sets in PIT, in Function Identity Testing, as norming sets ([1]) or in Reproducing Kernel Hilbert Spaces context. We generalize the main statement of [27] proving that short correct test sequences for lists of polynomials are densely distributed in any constructible set of accurate co-dimension and degree. In order to prove this result we introduce and develop the theory of degree of constructible sets, generalizing [25] and proving two Bezout's Inequalities for two different notions of degree. We exhibit the strength and limitations of correct test sequences with a randomized efficient algorithm for the "Suite Secante" Problem. Our algorithm generalizes [27], admitting a bigger class of sampling sets, also proving that PIT is in RPK. We reformulate, prove and generalize two results of the Polynomial Method: Dvir's exponential lower bounds for Kakeya sets and Alon's Combinatorial Nullstellensatz. (C) 2021 Elsevier Inc. All rights reserved.

著录项

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号