Scholarlink

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to \(\log n\) factor, for any Boolean function composed with \(\textsf{AND}\) function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of well-studied Boolean complexity measures like block sensitivity and certificate complexity. The relationship between the standard measures has been a long line of research, with a landmark result by Huang (Annals of Mathematics 2019), finally showing that sensitivity is polynomially related to all other standard measures. In this article, we study the monotone analogues of standard measures like block sensitivity ( \(\textsf{mbs}(f)\) ), certificate complexity ( \(\textsf{MCC}(f)\) ) and fractional block sensitivity ( \(\textsf{fmbs}(f)\) ); and study the relationship between these measures given their connection with \(\textsf{AND}\) -decision tree and sparsity of a Boolean function. We show the following results:

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Relations Between Monotone Complexity Measures Based on Decision Tree Complexity

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Farzan Byramji,
  • Vatsal Jha,
  • Chandrima Kayal,
  • Rajat Mittal

摘要

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to \(\log n\) factor, for any Boolean function composed with \(\textsf{AND}\) function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of well-studied Boolean complexity measures like block sensitivity and certificate complexity. The relationship between the standard measures has been a long line of research, with a landmark result by Huang (Annals of Mathematics 2019), finally showing that sensitivity is polynomially related to all other standard measures. In this article, we study the monotone analogues of standard measures like block sensitivity ( \(\textsf{mbs}(f)\) ), certificate complexity ( \(\textsf{MCC}(f)\) ) and fractional block sensitivity ( \(\textsf{fmbs}(f)\) ); and study the relationship between these measures given their connection with \(\textsf{AND}\) -decision tree and sparsity of a Boolean function. We show the following results: