Query-to-Communication Lifting Using Low-Discrepancy Gadgets
From MaRDI portal
Publication:5856149
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
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
