论文标题
反转高度的非交通性有理公式的黑盒标识测试在确定性的准化性时间中
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
论文作者
论文摘要
Hrubeš和Wigderson（2015）启动了与逆门的非交通公式的复杂性理论研究。他们引入了理性身份测试（RIT）问题，即确定非交通性有理公式是否在自由偏斜字段中计算为零。在白色盒子环境中，确定性的多项式时间算法以此问题而闻名，因为Garg，Gurvits，Oliveira和Wigderson（2016）和Ivanyos，Qiao和Subrahmanyam（2018）。 该领域的一个主要开放问题是设计有效公式的有效的确定性黑盒身份测试算法。在本文中，我们解决了第一个嵌套的反情况下解决此问题。更确切地说，我们通过击球设置的结构获得了反转高度的非交通性合理公式的确定性准化性时间黑盒RIT算法。击球集结构涉及几种新的技术思想，包括矩阵系数实现理论（Volčič，2018年）的关键概念和环状分区代数的特性（Lam，2001）。在通往证明的途中，一个重要的步骤是将撞击的福布斯和shpilka嵌入非交通公式（2013）中的循环分区代数中。
Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including key concepts from matrix coefficient realization theory (Volčič, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.
