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

文章基本信息

  • 标题:Does robustness imply tractability? A lower bound for planted clique in the semi-random model
  • 本地全文:下载
  • 作者:Jacob Steinhardt
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We consider a robust analog of the planted clique problem. In this analog, a set S of vertices is chosen and all edges in S are included; then, edges between S and the rest of the graph are included with probability 2 1 , while edges not touching S are allowed to vary arbitrarily. For this semi-random model, we show that the information-theoretic threshold for recovery is ( n ) , in sharp contrast to the classical information-theoretic threshold of ( log ( n )) . This matches the conjectured computational threshold for the classical planted clique problem, and thus raises the intriguing possibility that, once we require robustness, there is no computational-statistical gap for planted clique.

  • 关键词:computational-statistical gap ; planted clique ; robust learning ; semi-random model
国家哲学社会科学文献中心版权所有