首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity
  • 本地全文:下载
  • 作者:Marco Carmosino ; Russell Impagliazzo ; Manuel Sabin
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires n k time, for some constant 1/2"> 1 2 , to count (note that these conjectures are significantly weaker than the usual ones made about these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations:

    - BPP can be decided in polynomial time using only n random bits on average over any efficient input distribution, for any constant 0"> 0

    - BPP can be decided in polynomial time with no randomness on average over the uniform distribution

    This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible. Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.

  • 关键词:average case complexity ; derandomization ; fine-grained complexity ; hardness versus randomness ; k-clique ; orthogonal vectors
国家哲学社会科学文献中心版权所有