scientific article; zbMATH DE number 7564429

DOI10.4230/LIPIcs.CCC.2019.29MaRDI QIDQ5091781

Joshua Brody, Eric Blais

Publication date: 27 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

decision treescommunication complexityquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

Unnamed Item ⋮ Query-to-Communication Lifting for BPP ⋮ Unnamed Item

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

This page was built for publication: