Query-To-Communication Lifting for BPP Using Inner Product

DOI10.4230/LIPIcs.ICALP.2019.35zbMath1495.68082OpenAlexW2966301123MaRDI QIDQ5091185

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

Publication date: 21 July 2022

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

zbMATH Keywords

inner productlifting theoremsBPP liftingdeterministic lifting

Mathematics Subject Classification ID

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

Related Items (4)

An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Simulation theorems via pseudo-random properties ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Quantum versus randomized communication complexity, with efficient players

Cites Work

• Separation of the monotone NC hierarchy
• How to compress interactive communication
• A strong direct product theorem for disjointness
• The Pattern Matrix Method
• Communication Lower Bounds via Critical Block Sensitivity
• Deterministic Communication vs. Partition Number
• Structure of Protocols for XOR Functions
• Lower Bounds for Elimination via Weak Regularity
• Amortized Communication Complexity
• From Expanders to Hitting Distributions and Simulation Theorems
• Monotone circuit lower bounds from resolution
• Simulation beats richness: new data-structure lower bounds
• Rectangles Are Nonnegative Juntas
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Query-To-Communication Lifting for BPP Using Inner Product