The NOF multiparty communication complexity of composed functions
From MaRDI portal
Publication:496305
DOI10.1007/s00037-013-0078-4zbMath1329.68103OpenAlexW2081819660WikidataQ62556715 ScholiaQ62556715MaRDI QIDQ496305
Publication date: 21 September 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0078-4
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ramsey theory (05D10)
Related Items
Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on multiparty communication complexity and the Hales-Jewett theorem ⋮ Unnamed Item ⋮ Communication Lower Bounds Using Directional Derivatives
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sets of integers that do not contain long arithmetic progressions
- Lower bounds and separations for constant depth multilinear circuits
- Disjointness is hard in the multiparty number-on-the-forehead model
- On Roth's theorem on progressions
- On the power of small-depth threshold circuits
- Property testing lower bounds via communication complexity
- Lower bounds for local versions of dimension reductions
- An ergodic Szemerédi theorem for commuting transformations
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Circuits and multi-party protocols
- On data structures and asymmetric communication complexity
- The space complexity of approximating the frequency moments
- The BNS lower bound for multi-party protocols is nearly optimal
- On ACC
- An improved construction of progression-free sets
- Fourier analysis for probabilistic communication complexity
- On triples in arithmetic progression
- Complexity of constructing solutions in the core based on synergies among coalitions
- Hypergraph regularity and the multidimensional Szemerédi theorem
- New bounds on cap sets
- ON A GENERALIZATION OF SZEMERÉDI'S THEOREM
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Decompositions, approximate structure, transference, and the Hahn-Banach theorem
- Languages with Bounded Multiparty Communication Complexity
- Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Rounds in Communication Complexity Revisited
- Communication Complexity of Simultaneous Messages
- Simultaneous messages vs. communication
- An Application of Hindman's Theorem to a Problem on Communication Complexity
- Quantum communication complexity of symmetric predicates
- Communication Complexity
- Multiparty Communication Complexity and Threshold Circuit Size of AC^0
- Communication Complexity and Quasi Randomness
- On a problem of Gowers
- The multiparty communication complexity of set disjointness
- The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
- On Certain Sets of Integers
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- The BNS-Chung criterion for multi-party communication complexity
