Randomized query composition and product distributions

DOI10.4230/LIPICS.STACS.2024.56MaRDI QIDQ6902664zbMATH OpenFDO

Authors Swagato Sanyal

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.56

zbMATH Keywords

analysis of Boolean functionsBoolean function complexitydecision treerandomized query complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Interactive compression for product distributions
• Lower bounds on probabilistic linear decision trees
• On the composition of randomized query complexity and approximate degree
• 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 power of many samples in query complexity
• The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Cited in

(2)

• Quantum sabotage complexity
• Lifting to randomized parity decision trees

This page was built for publication: Randomized query composition and product distributions

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