Amortized Communication Complexity
From MaRDI portal
Publication:4852622
DOI10.1137/S0097539792235864zbMath0830.68070OpenAlexW2110110846MaRDI QIDQ4852622
Moni Naor, Eyal Kushilevitz, Noam Nisan, Tomás Feder
Publication date: 28 January 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792235864
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Communication theory (94A05) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15)
Related Items (26)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Interactive Information Complexity ⋮ Upper bounds on the Boolean rank of Kronecker products ⋮ Interactive Information Complexity ⋮ Direct sum fails for zero-error average communication ⋮ Certifying equality with limited interaction ⋮ Sharing one secret vs. sharing many secrets. ⋮ The communication complexity of functions with large outputs ⋮ Communication and information complexity ⋮ Query-to-Communication Lifting for BPP ⋮ The choice and agreement problems of a random function ⋮ Information complexity and applications. ⋮ The direct sum of universal relations ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions ⋮ Partition arguments in multiparty communication complexity ⋮ Unnamed Item ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parallel Repetition of the Odd Cycle Game ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets
This page was built for publication: Amortized Communication Complexity
