All classical adversary methods are equivalent for total functions

DOI10.4230/LIPICS.STACS.2018.8MaRDI QIDQ3304102zbMATH OpenOpenAlexFDO

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

Publication date 5 August 2020

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

zbMATH Keywords

adversary boundsfractional block sensitivitylower boundsrandomized query complexity

Mathematics Subject Classification ID

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

Abstract: We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $extfbs(f)$. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between $extfbs(f)$ and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than $sqrtncdotextbs(f)$, where $n$ is the number of variables and $extbs(f)$ is the block sensitivity. Then we exhibit a partial function $f$ that matches this upper bound, $extfbs(f)=Omega(sqrtncdotextbs(f))$.

Recommendations

• All Classical Adversary Methods Are Equivalent for Total Functions
• scientific article
• Automata, Languages and Programming
• On fractional block sensitivity
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments

Cites work

• An introduction to Kolmogorov complexity and its applications
• Complexity measures and decision tree complexity: a survey.
• Composition limits and separating examples for some Boolean function complexity measures
• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• Lower Bounds for Local Search by Quantum Arguments
• On fractional block sensitivity
• On the degree of Boolean functions as real polynomials
• Properties and applications of Boolean function composition
• Quantum certificate complexity
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Randomized query complexity of sabotaged and composed functions
• Separations in query complexity using cheat sheets
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

Cited in

(4)

• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• All Classical Adversary Methods Are Equivalent for Total Functions
• Automata, Languages and Programming
• The power of many samples in query complexity

This page was built for publication: All classical adversary methods are equivalent for total functions

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