Publication:5091781
From MaRDI portal
DOI10.4230/LIPIcs.CCC.2019.29MaRDI QIDQ5091781
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1908.01020
68Q25: Analysis of algorithms and problem complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal direct sum results for deterministic and randomized decision tree complexity
- An information statistics approach to data stream and communication complexity
- Improved direct product theorems for randomized query complexity
- Towards proving strong direct product theorems
- Decision trees with Boolean threshold queries
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Robust polynomials and quantum algorithms
- How to Compress Interactive Communication
- Information Equals Amortized Communication
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- Products and Help Bits in Decision Trees
- The Power of Asymmetry in Constant-Depth Circuits
- Deterministic Communication vs. Partition Number
- Separations in Query Complexity Based on Pointer Functions
- Amortized Communication Complexity
- Towards Better Separation between Deterministic and Randomized Query Complexity
- Separations in query complexity using cheat sheets
- Exponential separation of communication and external information
- Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
