Query-to-communication lifting for BPP using inner product

DOI10.4230/LIPICS.ICALP.2019.35MaRDI QIDQ5091185zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.ICALP.2019.35

zbMATH Keywords

BPP liftingdeterministic liftinginner productlifting theorems

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Measures of information, entropy (94A17)

Recommendations

• Query-to-communication lifting for BPP
• Query-to-communication lifting using low-discrepancy gadgets
• A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)

Cites work

• A strong direct product theorem for disjointness
• Amortized Communication Complexity
• Communication lower bounds via critical block sensitivity
• Deterministic communication vs. partition number
• From expanders to hitting distributions and simulation theorems
• How to compress interactive communication
• scientific article; zbMATH DE number 5568623 (Why is no real title available?)
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• scientific article; zbMATH DE number 6789270 (Why is no real title available?)
• Lower bounds for elimination via weak regularity
• Monotone circuit lower bounds from resolution
• Rectangles are nonnegative juntas
• Separation of the monotone NC hierarchy
• Simulation beats richness: new data-structure lower bounds
• Structure of protocols for XOR functions
• The pattern matrix method

Cited in

(9)

• Quantum versus randomized communication complexity, with efficient players
• Simulation theorems via pseudo-random properties
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for BPP
• Query-to-communication lifting using low-discrepancy gadgets
• An Optimal Separation of Randomized and Quantum Query Complexity
• Quantum lower bounds by sample-to-query lifting
• Quantum versus randomized communication complexity, with efficient players

This page was built for publication: Query-to-communication lifting for BPP using inner product

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