6533b86efe1ef96bd12cc713
RESEARCH PRODUCT
Upper bounds on multiparty communication complexity of shifts
Andris Ambainissubject
TheoryofComputation_MISCELLANEOUSDiscrete mathematicsCombinatoricsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYCommunication complexityBinary logarithmBoolean functionUpper and lower boundsMultiparty communicationMathematicsdescription
We consider some communication complexity problems which arise when proving lower bounds on the complexity of Boolean functions. In particular, we prove an \(O(\frac{n}{{2\sqrt {\log n} }}\log ^{1/4} n)\)upper bound on 3-party communication complexity of shifts, an O(n e ) upper bound on the multiparty communication complexity of shifts for a polylogarithmic number of parties. These bounds are all significant improvements over ones recently considered “unexpected” by Pudlak [5].
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1996-01-01 |