Query-to-Communication Lifting Using Low-Discrepancy Gadgets

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

lifting communication complexity query complexity

Mathematics Subject Classification ID

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

Related Items (2)

Lifting query complexity to time-space complexity for two-way finite automata ⋮ On the binary and Boolean rank of regular matrices

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