Hardness-Randomness Tradeoffs for Algebraic Computation
Hardness-Randomness Tradeoffs for Algebraic Computation
复制标题
代数计算的硬度-随机权衡
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ramprasad Saptharishi
中科院分区：
文献类型：
--
作者：
Mrinal Kumar;Ramprasad Saptharishi
证明下界问题和去随机化问题之间的相互作用，在不同的背景下，是复杂性理论的中心主题之一。在这篇综述中，我们从代数复杂性理论的角度来探讨这一现象。在此过程中，我们讨论了一些经典的结果，以及最近的一些结果，它们建立了代数电路下界证明问题和去随机化多项式恒等式检验问题之间的密切联系。我们还讨论了这种机器在多项式恒等式检验的自举现象中的应用，并提到了一些公开的问题。
The interplay between the question of proving lower bounds and that of derandomization, in various settings, is one of the central themes in complexity theory. In this survey, we explore this phenomenon in the area of algebraic complexity theory. Enroute, we discuss some of the classical results, as well as some recent ones, that establish a close connection between the question of proving algebraic circuits lower bounds and that of derandomizing polynomial identity testing. We also talk about an application of this machinery to the phenomenon of bootstrapping for polynomial identity testing and mention some open problems.