Communication Complexity

DOI10.1017/CBO9780511574948zbMATH Open0869.68048OpenAlexW605043455MaRDI QIDQ4875692FDOQ4875692

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)

information networks decision trees Boolean circuits communication complexity VLSI circuits coding theory Turing 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 Communication Complexity of Non-signaling Distributions
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
On Toda’s Theorem in Structural Communication Complexity
New results on the most significant bit of integer multiplication
One-way multiparty communication lower bound for pointer jumping with applications
Best-order streaming model
Kolmogorov complexity and combinatorial methods in communication complexity
A note on efficient aggregate queries in sensor networks
Exact OBDD bounds for some fundamental functions
Extremal problems under dimension constraints.
Computational hardness of optimal fair computation: beyond Minicrypt
Partition arguments in multiparty communication complexity
From quantum query complexity to state complexity
Multiparty communication complexity and very hard functions
An additive combinatorics approach relating rank to communication complexity
Generalizations of the distributed Deutsch-Jozsa promise problem
Unbounded-Error Classical and Quantum Communication Complexity
Construction of Very Hard Functions for Multiparty Communication Complexity
Linear algebraic methods in communication complexity
Space-bounded communication complexity
Introduction to computer science and economic theory
Traced communication complexity of cellular automata
Communication complexity in number-conserving and monotone cellular automata
Larger lower bounds on the OBDD complexity of integer multiplication
Exponential separation of quantum and classical online space complexity
Tight lower bounds for query processing on streaming and external memory data
Sharing the cost of multicast transmissions
On the power of Las Vegas II: Two-way finite automata
The communication cost of selfishness
Communication with contextual uncertainty
Finding large 3-free sets. I. The small \(n\) case
Distributed spanner approximation
A note on the size of OBDDs for the graph of integer multiplication
Informational requirements of social choice rules
Hardness results for multicast cost sharing.
On the communication complexity of approximate Nash equilibria
Title not available (Why is that?)
Lower Bounds for Testing Computability by Small Width OBDDs
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
Simulation of equatorial von Neumann measurements on GHZ states using nonlocal resources
On the memory requirements of XPath evaluation over XML streams
Communication complexity method for measuring nondeterminism in finite automata
Cellular automata and communication complexity
Comparing multiagent systems research in combinatorial auctions and voting
On complexity of single-minded auction
Individual communication complexity
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
Distributed averaging on digital erasure networks
Multiparty communication complexity of vector-valued and sum-type functions
Lower bounds for predecessor searching in the cell probe model
On the P versus NP intersected with co-NP question in communication complexity
Asking questions
On relations between counting communication complexity classes
New applications of the incompressibility method. II
The NOF multiparty communication complexity of composed functions
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
Bundling equilibrium in combinatorial auctions
Boosting distinct random sampling for basic counting on the union of distributed streams
Distinguishing two probability ensembles with one sample from each ensemble
On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
Protocols for asymmetric communication channels
Adventures in monotone complexity and TFNP
Testing computability by width-two OBDDs
Memory lower bounds for XPath evaluation over XML streams
Some upper and lower bounds on PSD-rank
The communication complexity of addition
Lower bounds for dynamic algebraic problems
Deterministic compression with uncertain priors
On multi-partition communication complexity
On the guessing number of shift graphs
New results for finding common neighborhoods in massive graphs in the data stream model
Communication complexity tools on recognizable picture languages
Property testing of the Boolean and binary rank
On the complexity of communication complexity
On the relative succinctness of sentential decision diagrams
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
STACS 2004
Ordered biclique partitions and communication complexity problems
\(\mathrm P \overset {?} {=} \mathrm{NP}\)
New bounds on the half-duplex communication complexity
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Communication complexity and linearly ordered sets
Exact OBDD Bounds for Some Fundamental Functions
On cover-structure graphs
The navigational power of web browsers
Dimension-free bounds and structural results in communication complexity
On the minimal Hamming weight of a multi-base representation
On the parity complexity measures of Boolean functions
Smallest formulas for the parity of \(2^k\) variables are essentially unique
The augmentation property of binary matrices for the binary and Boolean rank
Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
A characterization of average case communication complexity
On finding common neighborhoods in massive graphs.
Approximation of boolean functions by combinatorial rectangles
Communication complexity of multi-processor systems
Communication costs in a geometric communication network
An adaptivity hierarchy theorem for property testing
On communication protocols that compute almost privately
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
An introductory course on communication complexity

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)