Amortized Communication Complexity (Preliminary Version)

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i. e. the communication complexity of simultaneously computing f on l instances, divided by l is studied. The authors present, both in the deterministic and the randomized model, functions with communication complexity Theta (log n) and amortized communication complexity O(1). They also give a general lower bound on the amortized communication complexity of any function f in terms of its communication complexity C(f). >

Authors

• Tomás Feder
• Eyal Kushilevitz
• Moni Naor

Keywords

• Complexity theory
• Protocols
• Costs
• Chromium
• Computer science
• Context
• Circuits
• Boolean functions
• Complex Communication
• Rectangular
• Lower Bound
• Functional Identification
• Part Of Domain
• Hash Function
• Communication Cost
• Step Test
• Hamming Distance
• Direct Sum
• Input Length
• Complex Protocols
• Boolean Function
• One-way Communication
• Random Bits
• Coding Tree
• Idea Of The Proof
• Number Of Strings
• Random String