A composition theorem for randomized query complexity

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.4230/LIPICS.FSTTCS.2017.10" rel="nofollow">DOI 10.4230/LIPICS.FSTTCS.2017.10</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/1491.68082" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W2963520412" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q5136299" rel="nofollow">MaRDI QID Q5136299</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q5136299" rel="nofollow">FDO</a>

Authors Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Publication date 25 November 2020

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

zbMATH Keywords

decision treesquery complexityXOR lemmacomposition theoremhardness amplificationquery algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11)

Abstract: Let the randomized query complexity of a relation for error probability $epsilon$ be denoted by $R_{e}psilon(cdot)$. We prove that for any relation $fsubseteq{0,1}^{n}imesmathcalR$ and Boolean function $g:{0,1}^{m}ightarrow0,1$, $R_{1/3}(fcirc{g}^n)=Omega(R_{4/9}(f)cdot{R}_{1/2-1/n^4}(g))$, where $fcirc{g}^n$ is the relation obtained by composing $f$ and $g$. We also show that $R_{1/3}left(fcircleft(g^{o}plu{s}_{O(logn)}ight{)}^{n}ight)=Omega(logncdot{R}_{4/9}(f)cdot{R}_{1/3}(g))$, where $g^{o}plu{s}_{O(logn)}$ is the function obtained by composing the xor function on $O(logn)$ bits and $g^t$.

Recommendations

• Randomized query complexity of sabotaged and composed functions
• scientific article; zbMATH DE number 6913819
• Improved direct product theorems for randomized query complexity
• A composition theorem for decision tree complexity
• On derandomized composition of Boolean functions

Cites work

• scientific article; zbMATH DE number 6789270 (Why is no real title available?)
• A composition theorem for decision tree complexity
• Approximating the AND-OR tree
• Complexity measures and decision tree complexity: a survey.
• On fractional block sensitivity
• On rank vs. communication complexity
• Properties and applications of Boolean function composition
• Randomized query complexity of sabotaged and composed functions
• Structure of protocols for XOR functions

Cited in

(10)

• On derandomized composition of Boolean functions
• Randomized query complexity of sabotaged and composed functions
• A composition theorem for decision tree complexity
• Lifting Theorems for Equality
• REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM
• Improved direct product theorems for randomized query complexity
• The Zero-Error Randomized Query Complexity of the Pointer Function
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Conflict complexity is lower bounded by block sensitivity

This page was built for publication: A composition theorem for randomized query complexity

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