Deterministic Communication vs. Partition Number

DOI10.1137/16M1059369zbMath1409.68115OpenAlexW2905458870WikidataQ128730974 ScholiaQ128730974MaRDI QIDQ4562279

No author found.

Publication date: 19 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1059369

zbMATH Keywords

partition numberdeterministic communication

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (32)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Around the log-rank conjecture ⋮ On differential privacy and adaptive data analysis with bounded space ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ On the binary and Boolean rank of regular matrices ⋮ Parity decision tree in classical-quantum separations for certain classes of Boolean functions ⋮ Irreducible subcube partitions ⋮ Structure of Protocols for XOR Functions ⋮ Query-to-Communication Lifting for BPP ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Unnamed Item ⋮ From Expanders to Hitting Distributions and Simulation Theorems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomized versus deterministic decision tree size ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ On derandomized composition of Boolean functions ⋮ Rectangles Are Nonnegative Juntas ⋮ Communication lower bounds of key-agreement protocols via density increment arguments ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 ⋮ Upper bounds on communication in terms of approximate rank ⋮ Adventures in monotone complexity and TFNP ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Unnamed Item ⋮ Communication Complexity of Pairs of Graph Families with Applications ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• The linear-array conjecture in communication complexity is false
• Expressing combinatorial optimization problems by linear programs
• Non-deterministic communication complexity with few witnesses
• A note on non-deterministic communication complexity with few witnesses
• Communication complexity towards lower bounds on circuit depth
• Complexity measures and decision tree complexity: a survey.
• On rank vs. communication complexity
• Separation of the monotone NC hierarchy
• Communication complexity of approximate Nash equilibria
• On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
• Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• The Pattern Matrix Method
• Separations in Query Complexity Based on Pointer Functions
• Communication Complexity
• Recent advances on the log-rank conjecture in communication complexity
• Towards Better Separation between Deterministic and Randomized Query Complexity
• Separations in query complexity using cheat sheets
• On the virtue of succinct proofs
• Rectangles Are Nonnegative Juntas
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Deterministic Communication vs. Partition Number