Randomized query composition and sabotage complexity

DOI10.1145/3747851MaRDI QIDQ6872357zbMATH OpenFDO

Authors Swagato Sanyal

Publication date 20 January 2026

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3747851

zbMATH Keywords

analysis of Boolean functionsquery complexityrandomized decision tree

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cites work

• A composition theorem for decision tree complexity
• A composition theorem for randomized query complexity
• A composition theorem for randomized query complexity via max-conflict complexity
• A tight composition theorem for the randomized query complexity of partial functions (extended abstract)
• Analysis of Boolean Functions
• Complexity measures and decision tree complexity: a survey.
• Interactive compression for product distributions
• Lower bounds on probabilistic linear decision trees
• On the composition of randomized query complexity and approximate degree
• Optimal Search on Some Game Trees
• Partition bound is quadratically tight for product distributions
• Properties and applications of Boolean function composition
• Quadratically tight relations for randomized query complexity
• Randomised composition and small-bias minimax
• Randomized communication versus partition number
• Randomized query complexity of sabotaged and composed functions
• Reimer's inequality and tardos' conjecture
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

This page was built for publication: Randomized query composition and sabotage complexity

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