Communication Complexity
From MaRDI portal
Publication:4875692
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
informationnetworksdecision treesBoolean circuitscommunication complexityVLSI circuitscoding theoryTuring macines
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
- 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
- Fooling views: a new lower bound technique for distributed computations under congestion
- Property testing lower bounds via a generalization of randomized parity decision trees
- Title not available (Why is that?)
- 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
- How long to Pareto efficiency?
- Redundancy in distributed proofs
- Redundancy in distributed proofs
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Message Lower Bounds via Efficient Network Synchronization
- Lower bounds for subgraph detection in the CONGEST model
- Local verification of global proofs
- 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
- Communication complexity (for algorithm designers)
- Resolution over linear equations modulo two
- Deterministic communication vs. partition number
- Query-to-communication lifting for BPP
- On the communication complexity of high-dimensional permutations
- 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
- The impact of locality in the broadcast congested clique model
- A stable marriage requires communication
- The role of randomness in the broadcast congested clique model
- A distributed algorithm for spectral sparsification of graphs with applications to data clustering
- The function-inversion problem: barriers and opportunities
- Communication lower bounds using directional derivatives
- Problems and invariants connected with bicliques and multicliques of graphs
- Depth lower bounds for monotone semi-unbounded fan-in circuits.
- Distributed monitoring of election winners
- Title not available (Why is that?)
- Optimal collapsing protocol for multiparty pointer jumping
- Tight bounds for single-pass streaming complexity of the set cover problem
- The communication complexity of graphical games on grid graphs
- The cost of fault tolerance in multi-party communication complexity
- 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
- Freezing, bounded-change and convergent cellular automata
- Fourier sparsity of \(\mathrm{GF}(2)\) polynomials
- 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
- Separation of unbounded-error models in multi-party communication complexity
- On multiparty communication with large versus unbounded error
- 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
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)
