Communication Complexity

DOI10.1017/CBO9780511574948zbMATH Open0869.68048OpenAlexW605043455MaRDI QIDQ4875692FDOQ4875692

Authors: Eyal Kushilevitz, Noam Nisan 

Publication date: 24 April 1996

Full work available at URL: https://doi.org/10.1017/cbo9780511574948

Recommendations

• scientific article; zbMATH DE number 1011685
• Communication complexity
• scientific article; zbMATH DE number 4197419
• Communication complexity (for algorithm designers)

zbMATH Keywords

informationnetworksdecision treesBoolean circuitscommunication complexityVLSI circuitscoding theoryTuring macines

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Communication theory (94A05)

Cited In (only showing first 100 items - show all)

• Finding the Median (Obliviously) with Bounded Space
• Space lower bounds for online pattern matching
• One-round multi-party communication complexity of distinguishing sums
• State succinctness of two-way finite automata with quantum and classical states
• The layer complexity of Arthur-Merlin-like communication
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• A second look at counting triangles in graph streams (corrected)
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• On the expressive power of CNF formulas of bounded tree- and clique-width
• On public-coin zero-error randomized communication complexity
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Clique versus independent set
• The communication complexity of the Hamming distance problem
• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Jump number of two-directional orthogonal ray graphs
• Experimental multipartner quantum communication complexity employing just one qubit
• Implausible consequences of superstrong nonlocality
• Separating OR, SUM, and XOR circuits
• Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
• Communication complexity and intrinsic universality in cellular automata
• Linear algebraic methods in communication complexity
• On probabilistic pushdown automata
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Exponential lower bounds for polytopes in combinatorial optimization
• New strong direct product results in communication complexity
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index
• Quantum communication and complexity.
• A three-party communication problem
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Hellinger volume and number-on-the-forehead communication complexity
• Interactive Information Complexity
• Limitations on quantum dimensionality reduction
• Trading bit, message, and time complexity of distributed algorithms
• An information statistics approach to data stream and communication complexity
• Fast Evaluation of Union-Intersection Expressions
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Networks cannot compute their diameter in sublinear time
• Monotone circuit lower bounds from resolution
• A note on monotone complexity and the rank of matrices
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Biclique covers and partitions
• Communication complexity method for measuring nondeterminism in finite automata
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• The communication requirements of efficient allocations and supporting prices
• Comparing the size of NFAs with and without \(\epsilon\)-transitions
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Proof labeling schemes
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Mechanism design with a restricted action space
• Lower bounds in communication complexity
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• Space Lower Bounds for Online Pattern Matching
• Approximating Boolean functions by OBDDs
• Lower bounds for predecessor searching in the cell probe model
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Certifying equality with limited interaction
• Direct sum fails for zero-error average communication
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Quantifying communication in synchronized languages
• A second look at counting triangles in graph streams
• Information lower bounds via self-reducibility
• The communication complexity of addition
• A linear lower bound on the unbounded error probabilistic communication complexity.
• An optimal bit complexity randomized distributed MIS algorithm
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Communication complexity
• The complexity of data aggregation in directed networks
• Derandomized parallel repetition theorems for free games
• Hadamard tensors and lower bounds on multiparty communication complexity
• Fooling-sets and rank
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Secret-Sharing Schemes: A Survey
• Quantum speed-up for unsupervised learning
• Quantum entanglement and the communication complexity of the inner product function
• Quantum weakly nondeterministic communication complexity
• The hardness of being private
• BDDs -- design, analysis, complexity, and applications.
• The complexity of quantum disjointness
• Communication complexity of pairs of graph families with applications
• The (minimum) rank of typical fooling-set matrices
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• A note on randomized mutual search.
• Lower bounds for linearly transformed OBDDs and FBDDs
• Euclidean distance matrices and separations in communication complexity theory
• Information complexity and applications.
• Communication complexity of approximate maximum matching in the message-passing model
• The Complexity of Complexity
• Title not available (Why is that?)
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Some improved bounds on communication complexity via new decomposition of cliques
• Non-interactive proofs of proximity
• On the black-box use of somewhat homomorphic encryption in noninteractive two-party protocols
• Rectangles are nonnegative juntas
• Recognition problems and communication complexity.
• The direct sum of universal relations
• Simulation theorems via pseudo-random properties

This page was built for publication: Communication Complexity

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