The communication complexity of addition (Q519955): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: The expressive power of voting polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simple Constructions of Almost k-wise Independent Random Variables / rank
 
Normal rank
Property / cites work
 
Property / cites work: When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4385519 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pseudorandom Bits for Polynomials / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5441000 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A discrepancy lower bound for information complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Communication Complexity and Quasi Randomness / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Reliable Randomized Algorithm for the Closest-Pair Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Complexity of Information Spreading in Dynamic Networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing with Noisy Information / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parity, circuits, and the polynomial-time hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Estimating the optimal margins of embeddings in Euclidean half spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3729902 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Majority gates vs. general weighted threshold gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning and Lower Bounds for AC 0 with Threshold Gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Size of Weights for Threshold Gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the power of small-depth threshold circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2762792 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Communication Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: One way functions and pseudorandom generators / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constant depth circuits, Fourier transform, and learnability / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Complexity vs Communication Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: On data structures and asymmetric communication complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Theory of majority decision elements / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5655273 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5628106 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4284623 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Synthesizers and their application to the parallel construction of pseudo-random functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Number-theoretic constructions of efficient pseudo-random functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pseudorandom Functions and Factoring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Randomness is linear in space / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perceptrons of large weight / rank
 
Normal rank
Property / cites work
 
Property / cites work: The BNS-Chung criterion for multi-party communication complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Natural proofs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hardness Amplification Proofs Require Majority / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3002796 / rank
 
Normal rank

Revision as of 14:21, 13 July 2024

scientific article
Language Label Description Also known as
English
The communication complexity of addition
scientific article

    Statements

    The communication complexity of addition (English)
    0 references
    0 references
    31 March 2017
    0 references
    From the summary: Suppose each of \(k\leq n^{o(1)}\) players holds an \(n\)-bit number \(x_i\) in its hand. The players wish to determine if \(\sum_{i\leq k}x_i =s\). We give a public-coin protocol with error 1\% and communication \(O(k \log k)\). The communication bound is independent of \(n\), and for \(k\geq 3\) improves on the \(O(k \log n)\) bound by \textit{N. Nisan} [in: Combinatorics, Paul Erdős is eighty. Vol. 1. Budapest: János Bolyai Mathematical Society. Bolyai Society Mathematical Studies. 301--315 (1993; Zbl 0790.94028)]. Our protocol also applies to addition modulo \(m\). In this case we give a matching (public-coin) \(\Omega (k \log k)\) lower bound for various \(m\). We also obtain some lower bounds over the integers, including \(\Omega (k \log \log k)\) for protocols that are one-way, like ours. We give a protocol to determine if \(\sum x_i >s\) with error 1\% and communication \(O(k\log k)\log n\). For \(k\geq 3\) this improves on Nisan's \(O(k \log^{2} n)\) bound. A similar improvement holds for computing degree-\((k-1)\) polynomial-threshold functions in the number-on-forehead model. We give a (public-coin, 2-player, tight) \(\Omega (\log n)\) lower bound to determine if \(x_1>x_2\). This improves on the \(\Omega(\sqrt{\log n})\) bound by Smirnov (1988). Troy Lee informed us in January 2013 that an \(\Omega(\log n)\) lower bound may also be obtained by combining a result in learning theory by \textit{J. Forster} et al. [Mach. Learn. 51, No. 3, 263--281 (2003; Zbl 1026.68112)] with a result by \textit{N. Linial} and \textit{A. Shraibman} [Comb. Probab. Comput. 18, No. 1--2, 227--245 (2009; Zbl 1202.68314)]. As an application, we show that polynomial size \(\mathrm{AC}^{0}\) circuits augmented with \(O\)(1) threshold (or symmetric) gates cannot compute cryptographic pseudorandom functions, extending the result about \(\mathrm{AC}^{0}\) by \textit{N. Linial} et al. [J. Assoc. Comput. Mach. 40, No. 3, 607--620 (1993; Zbl 0781.94006)].
    0 references
    0 references
    public-coin protocol
    0 references
    addition modulo \(m\)
    0 references
    number-on-forehead model
    0 references
    cryptographic pseudorandom function
    0 references
    sum-equal problem
    0 references
    communication protocol
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers