The communication complexity of addition

DOI10.1007/S00493-014-3078-3zbMATH Open1374.68228OpenAlexW3137429815MaRDI QIDQ519955FDOQ519955

Authors: Emanuele Viola 

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

Recommendations

• The communication complexity of addition
• Communication complexity of some number theoretic functions
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• One-round multi-party communication complexity of distinguishing sums
• Separating deterministic from randomized multiparty communication complexity

zbMATH Keywords

communication protocoladdition modulo \(m\)cryptographic pseudorandom functionnumber-on-forehead modelpublic-coin protocolsum-equal problem

Mathematics Subject Classification ID

Cryptography (94A60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• Computing with Noisy Information
• Communication Complexity
• The expressive power of voting polynomials
• A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
• Constant depth circuits, Fourier transform, and learnability
• On the complexity of information spreading in dynamic networks
• One way functions and pseudorandom generators
• Majority gates vs. general weighted threshold gates
• Parity, circuits, and the polynomial-time hierarchy
• On the power of small-depth threshold circuits
• Title not available (Why is that?)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Title not available (Why is that?)
• Communication Complexity and Quasi Randomness
• The BNS-Chung criterion for multi-party communication complexity
• Estimating the optimal margins of embeddings in Euclidean half spaces
• Hardness Amplification Proofs Require Majority
• Natural proofs
• Randomness is linear in space
• Pseudorandom bits for polynomials
• Number-theoretic constructions of efficient pseudo-random functions
• Title not available (Why is that?)
• Logarithmic forms and Diophantine geometry
• Title not available (Why is that?)
• On data structures and asymmetric communication complexity
• Norms, XOR lemmas, and lower bounds for polynomials and protocols
• Learning complexity vs communication complexity
• On the Size of Weights for Threshold Gates
• Theory of majority decision elements
• Perceptrons of large weight
• Pseudorandom Functions and Factoring
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• Title not available (Why is that?)
• Synthesizers and their application to the parallel construction of pseudo-random functions
• Title not available (Why is that?)

Cited In (12)

• One-round multi-party communication complexity of distinguishing sums
• The cost of the missing bit: Communication complexity with help
• Dimension-free bounds and structural results in communication complexity
• The communication complexity of functions with large outputs
• Rectangles are nonnegative juntas
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Exponential separation of communication and external information
• Arithmetic sketching
• Simplified separation of information and communication
• The communication complexity of addition
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Communication complexity of some number theoretic functions

This page was built for publication: The communication complexity of addition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519955)