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

文章基本信息

  • 标题:Succinct and explicit circuits for sorting and connectivity
  • 本地全文:下载
  • 作者:Hamidreza Jahanjou ; Eric Miles ; Emanuele Viola
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC2 circuits whose connections can be computed with constant locality.

  • 关键词:circuit; connectivity; sorting; Uniformity
国家哲学社会科学文献中心版权所有