The communication complexity of addition
From MaRDI portal
Publication:519955
DOI10.1007/S00493-014-3078-3zbMath1374.68228OpenAlexW3137429815MaRDI QIDQ519955
Publication date: 31 March 2017
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-014-3078-3
communication protocoladdition modulo \(m\)cryptographic pseudorandom functionnumber-on-forehead modelpublic-coin protocolsum-equal problem
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60)
Related Items (8)
The communication complexity of functions with large outputs ⋮ Arithmetic sketching ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Rectangles Are Nonnegative Juntas ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Unnamed Item ⋮ A counter-example to the probabilistic universal graph conjecture via randomized communication complexity ⋮ Exponential Separation of Communication and External Information
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A discrepancy lower bound for information complexity
- On the power of small-depth threshold circuits
- Perceptrons of large weight
- One way functions and pseudorandom generators
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Majority gates vs. general weighted threshold gates
- On data structures and asymmetric communication complexity
- Synthesizers and their application to the parallel construction of pseudo-random functions
- The expressive power of voting polynomials
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Estimating the optimal margins of embeddings in Euclidean half spaces
- Randomness is linear in space
- A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
- Theory of majority decision elements
- Pseudorandom Bits for Polynomials
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Constant depth circuits, Fourier transform, and learnability
- Pseudorandom Functions and Factoring
- Number-theoretic constructions of efficient pseudo-random functions
- Parity, circuits, and the polynomial-time hierarchy
- Learning Complexity vs Communication Complexity
- Learning and Lower Bounds for AC 0 with Threshold Gates
- Simple Constructions of Almost k-wise Independent Random Variables
- On the Size of Weights for Threshold Gates
- Computing with Noisy Information
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Communication Complexity
- Communication Complexity and Quasi Randomness
- Hardness Amplification Proofs Require Majority
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- On the Complexity of Information Spreading in Dynamic Networks
- Natural proofs
- The BNS-Chung criterion for multi-party communication complexity
This page was built for publication: The communication complexity of addition
