All Classical Adversary Methods Are Equivalent for Total Functions

DOI10.1145/3442357zbMath1487.68118OpenAlexW3126717060MaRDI QIDQ5061885

Krišjānis Prūsis, Jevgēnijs Vihrovs, Martins Kokainis, Aleksejs Zajakins, Andris Ambainis

Publication date: 14 March 2022

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8495/

zbMATH Keywords

lower boundsfractional block sensitivityrandomized query complexityadversary bounds

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)

This page was built for publication: All Classical Adversary Methods Are Equivalent for Total Functions