Deterministic Communication vs. Partition Number
From MaRDI portal
Publication:4562279
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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (28)
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 ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ On derandomized composition of Boolean functions ⋮ Rectangles Are Nonnegative Juntas ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ 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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Deterministic Communication vs. Partition Number
