Nearly optimal separations between communication (or query) complexity and partitions

DOI10.4230/LIPICS.CCC.2016.4MaRDI QIDQ5368738zbMATH OpenFDO

Authors Martins Kokainis, Robin Kothari, Andris Ambainis

Publication date 10 October 2017

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

zbMATH Keywords

communication complexitypartition boundquery complexitysubcube partition complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Separations in query complexity using cheat sheets
• Partition bound is quadratically tight for product distributions
• scientific article; zbMATH DE number 7204275

Cited in

(14)

• Optimal separation in exact query complexities for Simon's problem
• On multi-partition communication complexity
• Deterministic communication vs. partition number
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Partition bound is quadratically tight for product distributions
• Low-sensitivity functions from unambiguous certificates
• Time-Space Complexity Advantages for Quantum Computing
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• Optimal separation and strong direct sum for randomized query complexity
• Query-to-communication lifting for BPP
• Separating decision tree complexity from subcube partition complexity
• Separations in query complexity using cheat sheets
• Proving unsatisfiability with hitting formulas
• Fooling near-maximal decision trees

This page was built for publication: Nearly optimal separations between communication (or query) complexity and partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368738)