Communication Complexity

DOI10.1017/CBO9780511574948zbMATH Open0869.68048OpenAlexW605043455MaRDI QIDQ4875692FDOQ4875692

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)

• The hardest halfspace
• Deciding and verifying network properties locally with few output bits
• Introduction to local certification
• Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
• Title not available (Why is that?)
• Trading information complexity for error. II: The case of a large error and the external information complexity
• Approximate proof-labeling schemes
• Equality alone does not simulate randomness
• Query-to-Communication Lifting for BPP
• Title not available (Why is that?)
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed construction of purely additive spanners
• Property testing lower bounds via a generalization of randomized parity decision trees
• Title not available (Why is that?)
• The Impact of Locality in the Broadcast Congested Clique Model
• Message lower bounds via efficient network synchronization
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Fast Private Norm Estimation and Heavy Hitters
• Simulation theorems via pseudo-random properties
• Title not available (Why is that?)
• Redundancy in distributed proofs
• Message Lower Bounds via Efficient Network Synchronization
• Interleaved Group Products
• Sign rank versus Vapnik-Chervonenkis dimension
• Upper bounds on the Boolean rank of Kronecker products
• Placing conditional disclosure of secrets in the communication complexity universe
• Resolution over linear equations modulo two
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Counting the number of perfect matchings, and generalized decision trees
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Freezing, Bounded-Change and Convergent Cellular Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• The role of randomness in the broadcast congested clique model
• A distributed algorithm for spectral sparsification of graphs with applications to data clustering
• Fourier Sparsity of GF(2) Polynomials
• The function-inversion problem: barriers and opportunities
• Intractability of min- and max-cut in streaming graphs
• Communication Lower Bounds Using Directional Derivatives
• Lower Bounds for Subgraph Detection in the CONGEST Model
• Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
• Title not available (Why is that?)
• Optimal collapsing protocol for multiparty pointer jumping
• The communication complexity of graphical games on grid graphs
• On the fastest Vickrey algorithm
• Automata, Languages and Programming
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Streaming algorithms for extent problems in high dimensions
• Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
• The Cost of Fault Tolerance in Multi-Party Communication Complexity
• Title not available (Why is that?)
• Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
• Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors
• Distributed adaptive Gaussian mean estimation with unknown variance: interactive protocol helps adaptation
• The binary rank of circulant block matrices
• On the decision tree complexity of threshold functions
• On the streaming indistinguishability of a random permutation and a random function
• Deterministic Communication vs. Partition Number
• The complexity of quantum disjointness
• Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)
• 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
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• 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?)
• 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
• Rectangles are nonnegative juntas
• Recognition problems and communication complexity.
• The direct sum of universal relations
• The unbounded-error communication complexity of symmetric functions
• On Slepian-Wolf theorem with interaction
• Algorithmic complexity of recursive and inductive algorithms
• Upper bounds on communication in terms of approximate rank
• The Communication Complexity of Set Intersection and Multiple Equality Testing
• The communication complexity of private simultaneous messages, revisited
• Search complexity: a way for the quantitative analysis of the search space
• Title not available (Why is that?)
• On the power of randomized multicounter machines
• Frequent directions: simple and deterministic matrix sketching
• The landscape of communication complexity classes
• Classical versus quantum communication in XOR games
• Privacy in non-private environments
• On minimally non-firm binary matrices
• On the Power of Learning from k-Wise Queries
• Cancellation-free circuits in unbounded and bounded depth
• The Communication Complexity of Distributed epsilon-Approximations
• Proof complexity of symbolic QBF reasoning
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Energy Complexity of Recurrent Neural Networks
• Title not available (Why is that?)
• Interval selection in the streaming model
• On the monotonicity of a data stream

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)