Query-to-Communication Lifting Using Low-Discrepancy Gadgets

DOI10.1137/19M1310153MaRDI QIDQ5856149

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

Publication date: 24 March 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

liftingcommunication complexityquery complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Lifting query complexity to time-space complexity for two-way finite automata ⋮ On the binary and Boolean rank of regular matrices ⋮ Randomized versus deterministic decision tree size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved direct product theorems for randomized query complexity
• On the distributional complexity of disjointness
• Communication complexity towards lower bounds on circuit depth
• Towards proving strong direct product theorems
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• Simulation theorems via pseudo-random properties
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• How to compress interactive communication
• A strong direct product theorem for disjointness
• Information Equals Amortized Communication
• The Pattern Matrix Method
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Parallelism in Comparison Problems
• Communication Lower Bounds via Critical Block Sensitivity
• Deterministic Communication vs. Partition Number
• Interactive Information Complexity
• Structure of Protocols for XOR Functions
• Amortized Communication Complexity
• Communication Complexity
• Strongly exponential lower bounds for monotone computation
• Query-To-Communication Lifting for BPP Using Inner Product
• Query-to-Communication Lifting for BPP
• Monotone circuit lower bounds from resolution
• Simulation beats richness: new data-structure lower bounds
• Lifting Nullstellensatz to monotone span programs over any field
• Exponential separation of communication and external information
• Rectangles Are Nonnegative Juntas
• Exponential Separation of Information and Communication for Boolean Functions
• Recognizing read-once functions from depth-three formulas

This page was built for publication: Query-to-Communication Lifting Using Low-Discrepancy Gadgets