Relations between monotone complexity measures based on decision tree complexity

DOI10.1007/978-981-96-1090-7_11MaRDI QIDQ6970739zbMATH OpenFDO

Authors Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal

Publication date 17 June 2025

Full work available at URL https://doi.org/10.1007/978-981-96-1090-7_11

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A tight composition theorem for the randomized query complexity of partial functions (extended abstract)
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Lifting Theorems for Equality
• Log-rank and lifting for AND-functions
• On fractional block sensitivity
• On rank vs. communication complexity
• On the degree of Boolean functions as real polynomials
• Properties and applications of Boolean function composition
• Separations in query complexity using cheat sheets

This page was built for publication: Relations between monotone complexity measures based on decision tree complexity

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