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

文章基本信息

  • 标题:Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
  • 本地全文:下载
  • 作者:Pavel Hrubes ; Sivaramakrishnan Natarajan Ramamoorthy ; Anup Rao
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-22
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S 1 S k [ n ] is balancing if for every subset X 1 2 n of size n 2 , there is an i [ k ] so that S i X = S i 2 . We extend and simplify the framework developed by Hegedüs for proving lower bounds on the size of balancing set families. We prove that if n = 2 p for a prime p , then k p . For arbitrary values of n , we show that k n 2 − o ( n ) .We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n 2 − o ( n ) . We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function.

国家哲学社会科学文献中心版权所有