A composition theorem for randomized query complexity

DOI10.4230/LIPICS.FSTTCS.2017.10zbMATH Open1491.68082arXiv1706.00335OpenAlexW2963520412MaRDI QIDQ5136299FDOQ5136299

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

Publication date: 25 November 2020

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$.

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

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

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)

Cites Work

• Complexity measures and decision tree complexity: a survey.
• On rank vs. communication complexity
• Title not available (Why is that?)
• Dual lower bounds for approximate degree and Markov-Bernstein inequalities
• Properties and applications of boolean function composition
• Title not available (Why is that?)
• Structure of Protocols for XOR Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Conflict complexity is lower bounded by block sensitivity
• REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Zero-Error Randomized Query Complexity of the Pointer Function
• Lifting Theorems for Equality

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)