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

文章基本信息

  • 标题:Lower Bounds for Linear Decision Lists
  • 本地全文:下载
  • 作者:Arkadev Chattopadhyay ; Meena Mahajan ; Nikhil Mande
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-18
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function MA J X O R requires size 2 0 18 n . This completely answers an open question of Tur{\'a}n and Vatan [FoCM'97]. We also show that the spectral classes P L 1 P L , and the polynomial threshold function classes P T 1 P T 1 , are incomparable to linear decision lists.

  • 关键词:Decision lists ; Threshold Circuits
国家哲学社会科学文献中心版权所有