Hardness Amplification for Non-Commutative Arithmetic Circuits

Marco L. Carmosino; Russell Impagliazzo; Shachar Lovett; Ivan Mihajlin

首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Hardness Amplification for Non-Commutative Arithmetic Circuits

【24h】

Hardness Amplification for Non-Commutative Arithmetic Circuits

机译：非交换算术电路的硬度放大

获取原文

获取外文期刊封面封底 >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.

机译：我们证明了证明非交换算术电路上的温和超线性下界意味着非交换算术电路上的指数下界。也就是说，非交换电路的复杂性是一个门槛现象：表面上很弱的下限实际上足以显示我们所希望的最强下限。版本的布尔复杂度，仍然不能证明一般设备上的超线性下限。人们可以将我们的工作视为积极的消息（足以证明弱的下界以获得强势的消息）或消极的消息（证明弱的下界与证明强的缺点一样困难）。我们将其留给读者确定自己的乐观水平。

著录项

来源
《LIPIcs : Leibniz International Proceedings in Informatics》 |2018年第23期|共16页
作者
Marco L. Carmosino; Russell Impagliazzo; Shachar Lovett; Ivan Mihajlin;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种
中图分类计算技术、计算机技术;
关键词
arithmetic circuitshardness amplificationcircuit lower boundsnon-commutative computation;

机译：算术电路硬度放大电路下界非交换计算;

相似文献

外文文献
中文文献
专利

1. Hardness Amplification for Non-Commutative Arithmetic Circuits [J] . Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Electronic Colloquium on Computational Complexity . 2018,第9期

机译：非交换算术电路的硬度放大
2. LOWER BOUNDS AND PIT FOR NON-COMMUTATIVE ARITHMETIC CIRCUITS WITH RESTRICTED PARSE TREES [J] . Lagarde Guillaume, Limaye Nutan, Srinivasan Srikanth Computational complexity . 2019,第3期

机译：带约束的稀疏树的非对流算术电路的下界和基坑
3. LOWER BOUNDS AND PIT FOR NON-COMMUTATIVE ARITHMETIC CIRCUITS WITH RESTRICTED PARSE TREES [J] . Lagarde Guillaume, Limaye Nutan, Srinivasan Srikanth Computational complexity . 2019,第3期

机译：具有限制解析树的非换向算术电路的下限和坑
4. Hardness-randomness tradeoffs for bounded depth arithmetic circuits [C] . Zeev Dvir, Amir Shpilka, Amir Yehudayoff Annual ACM symposium on Theory of computing;ACM symposium on Theory of computing . 2008

机译：有界深度算术电路的硬度-随机性折衷
5. Hardness assurance testing and radiation hardening by design techniques for silicon-germanium heterojunction bipolar transistors and digital logic circuits. [D] . Sutton, Akil K. 2009

机译：通过设计技术对硅锗异质结双极晶体管和数字逻辑电路进行硬度保证测试和辐射硬化。
6. A novel reversible logic gate and its systematic approach to implement cost-efficient arithmetic logic circuits using QCA [O] . Peer Zahoor Ahmad, S.M.K. Quadri, Firdous Ahmad, 2017

机译：一种使用QCA实现具有成本效益的算术逻辑电路的新型可逆逻辑门及其系统方法
7. Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees [O] . Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan 2018

机译：具有限制解析树的非换向算术电路的下限和坑
8. Radiation Hardness Assurance Testing of Microelectronic Devices and Integrated Circuits: Radiation Environments, Physical Mechanisms, and Foundation for Hardness Assurance. [R] . Schwank, J. R., Shaneyflet, M. R., Dodd, P. E. 2008

机译：微电子器件和集成电路的辐射硬度保证测试：辐射环境，物理机制和硬度保证基础。

Hardness Amplification for Non-Commutative Arithmetic Circuits

摘要

著录项

相似文献

相关主题

期刊订阅