Conflict complexity is lower bounded by block sensitivity

DOI10.1016/J.TCS.2020.12.038MaRDI QIDQ2219069zbMATH OpenOpenAlexFDO

Authors Yaqiao Li

Publication date 19 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.08873

zbMATH Keywords

block sensitivitycertificate complexityconflict complexitydecision trees

Mathematics Subject Classification ID

Boolean functions (06E30) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: We show conflict complexity of every total Boolean function, recently introduced in [Swagato Sanyal. A composition theorem via conict complexity. arXiv preprint arXiv:1801.03285, 2018.] to prove a composition theorem of randomized decision tree complexity, is at least a half of its block sensitivity. We propose to compare conflict complexity with certificate complexity, and explain why it could be interesting.

Recommendations

• Sensitivity versus certificate complexity of Boolean functions
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Complexity measures and decision tree complexity: a survey.

Cites work

• A composition theorem for randomized query complexity
• A composition theorem for randomized query complexity via max-conflict complexity
• Communication lower bounds via critical block sensitivity
• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On fractional block sensitivity
• Sensitivity vs. block sensitivity of Boolean functions
• Tighter relations between sensitivity and other complexity measures

Cited in

(1)

• A composition theorem for randomized query complexity via max-conflict complexity

This page was built for publication: Conflict complexity is lower bounded by block sensitivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219069)