License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.63
URN: urn:nbn:de:0030-drops-188883
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18888/
Chakraborty, Sourav ;
Kayal, Chandrima ;
Mittal, Rajat ;
Paraashar, Manaswi ;
Sanyal, Swagato ;
Saurabh, Nitin
On the Composition of Randomized Query Complexity and Approximate Degree
Abstract
For any Boolean functions f and g, the question whether R(f∘g) = Θ̃(R(f) ⋅ R(g)), is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg̃(f∘g) = Θ̃(deg̃(f)⋅deg̃(g)). These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily.
It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R and deg̃ compose.
A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g) = Ω(noisyR(f)⋅ R(g)). This implies that composition holds whenever noisyR(f) = Θ̃(R(f)). We show two results:
1. When R(f) = Θ(n), then noisyR(f) = Θ(R(f)). In other words, composition holds whenever the randomized query complexity of the outer function is full.
2. If R composes with respect to an outer function, then noisyR also composes with respect to the same outer function. On the other hand, no result of the type deg̃(f∘g) = Ω(M(f) ⋅ deg̃(g)) (for some non-trivial complexity measure M(⋅)) was known to the best of our knowledge. We prove that deg̃(f∘g) = Ω̃(√{bs(f)} ⋅ deg̃(g)), where bs(f) is the block sensitivity of f. This implies that deg̃ composes when deg̃(f) is asymptotically equal to √{bs(f)}.
It is already known that both R and deg̃ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
BibTeX - Entry
@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2023.63,
author = {Chakraborty, Sourav and Kayal, Chandrima and Mittal, Rajat and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
title = {{On the Composition of Randomized Query Complexity and Approximate Degree}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {63:1--63:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-296-9},
ISSN = {1868-8969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18888},
URN = {urn:nbn:de:0030-drops-188883},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.63},
annote = {Keywords: Approximate degree, Boolean functions, Composition Theorem, Partial functions, Randomized Query Complexity}
}
|
Keywords: |
|
Approximate degree, Boolean functions, Composition Theorem, Partial functions, Randomized Query Complexity |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
04.09.2023 |
