Communication Complexity
From MaRDI portal
Publication:4875692
DOI10.1017/CBO9780511574948zbMath0869.68048OpenAlexW605043455MaRDI QIDQ4875692
Publication date: 24 April 1996
Full work available at URL: https://doi.org/10.1017/cbo9780511574948
informationnetworksdecision treescoding theoryVLSI circuitscommunication complexityBoolean circuitsTuring macines
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Communication theory (94A05)
Related Items
Implausible consequences of superstrong nonlocality, Experimental multipartner quantum communication complexity employing just one qubit, Separating OR, SUM, and XOR circuits, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, Communication with contextual uncertainty, Property testing of the Boolean and binary rank, The corruption bound, log-rank, and communication complexity, New bounds on the half-duplex communication complexity, Hellinger volume and number-on-the-forehead communication complexity, An adaptivity hierarchy theorem for property testing, The communication cost of selfishness, Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance, The communication complexity of the Hamming distance problem, A characterization of average case communication complexity, Zero-information protocols and unambiguity in Arthur-Merlin communication, A direct product theorem for two-party bounded-round public-coin communication complexity, Direct sum fails for zero-error average communication, Certifying equality with limited interaction, A discrepancy lower bound for information complexity, Quantifying communication in synchronized languages, Approximating Boolean functions by OBDDs, A note on efficient aggregate queries in sensor networks, On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata, Multiparty communication complexity and very hard functions, An information statistics approach to data stream and communication complexity, Derandomized parallel repetition theorems for free games, Hadamard tensors and lower bounds on multiparty communication complexity, Tight bounds for distributed minimum-weight spanning tree verification, On the memory requirements of XPath evaluation over XML streams, Simulation of equatorial von Neumann measurements on GHZ states using nonlocal resources, Quantum entanglement and the communication complexity of the inner product function, Quantum weakly nondeterministic communication complexity, A broader view on the limitations of information processing and communication by nature, Space lower bounds for online pattern matching, State succinctness of two-way finite automata with quantum and classical states, One-round multi-party communication complexity of distinguishing sums, Communication complexity and intrinsic universality in cellular automata, Comparing multiagent systems research in combinatorial auctions and voting, On the expressive power of CNF formulas of bounded tree- and clique-width, Clique versus independent set, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Biclique covers and partitions, Adapting parallel algorithms to the W-stream model, with applications to graph problems, Approximation of boolean functions by combinatorial rectangles, Hardness results for multicast cost sharing., Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines., Linear algebraic methods in communication complexity, Distributed averaging on digital erasure networks, Extremal problems under dimension constraints., Weak derandomization of weak algorithms: explicit versions of Yao's lemma, A counterexample to the Alon-Saks-Seymour conjecture and related problems, Recognition problems and communication complexity., A lower bound for integer multiplication on randomized ordered read-once branching programs., BDDs -- design, analysis, complexity, and applications., Finding large 3-free sets. I. The small \(n\) case, Memory lower bounds for XPath evaluation over XML streams, An optimal bit complexity randomized distributed MIS algorithm, Algorithmic complexity of recursive and inductive algorithms, Asking questions, The NOF multiparty communication complexity of composed functions, Boosting distinct random sampling for basic counting on the union of distributed streams, Distinguishing two probability ensembles with one sample from each ensemble, Information lower bounds via self-reducibility, Some upper and lower bounds on PSD-rank, New results for finding common neighborhoods in massive graphs in the data stream model, Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity, The communication complexity of addition, One-way multiparty communication lower bound for pointer jumping with applications, The navigational power of web browsers, Kolmogorov complexity and combinatorial methods in communication complexity, Best-order streaming model, On cover-structure graphs, Partition arguments in multiparty communication complexity, How long to equilibrium? The communication complexity of uncoupled equilibrium procedures, Traced communication complexity of cellular automata, Communication complexity in number-conserving and monotone cellular automata, On the parity complexity measures of Boolean functions, Smallest formulas for the parity of \(2^k\) variables are essentially unique, Larger lower bounds on the OBDD complexity of integer multiplication, A note on the size of OBDDs for the graph of integer multiplication, On communication protocols that compute almost privately, On probabilistic pushdown automata, Exponential separation of quantum and classical online space complexity, A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs, A second look at counting triangles in graph streams, Choosing, agreeing, and eliminating in communication complexity, Tradeoff lower lounds for stack machines, Lower bounds on nonnegative rank via nonnegative nuclear norms, Extended formulations, nonnegative factorizations, and randomized communication protocols, Informational requirements of social choice rules, A note on monotone complexity and the rank of matrices, On the guessing number of shift graphs, A three-party communication problem, New bounds on classical and quantum one-way communication complexity, Testing computability by width-two OBDDs, Toward better depth lower bounds: two results on the multiplexor relation, On the P versus NP intersected with co-NP question in communication complexity, Protocols for asymmetric communication channels, A note on randomized mutual search., Lower bounds for linearly transformed OBDDs and FBDDs, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, On the Decision Tree Complexity of Threshold Functions, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices, Circulant almost cross intersecting families, Time-Space Complexity Advantages for Quantum Computing, Anticoncentration and the Exact Gap-Hamming Problem, Worst-case asymmetric distributed function computation, A Short List of Equalities Induces Large Sign-Rank, Sequential Relational Decomposition, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols, On (simple) decision tree rank, Around the log-rank conjecture, Communication costs in a geometric communication network, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Query Complexity of Sampling and Small Geometric Partitions, Query-to-Communication Lifting for BPP, Unnamed Item, Unnamed Item, Energy Complexity of Recurrent Neural Networks, Deterministic compression with uncertain priors, Foundations of Homomorphic Secret Sharing, Unbounded-Error Classical and Quantum Communication Complexity, Fast Evaluation of Union-Intersection Expressions, ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES, Approximate F_2-Sketching of Valuation Functions, String Matching: Communication, Circuits, and Learning., From Expanders to Hitting Distributions and Simulation Theorems, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems, On Slepian–Wolf Theorem with Interaction, Fourier Sparsity of GF(2) Polynomials, On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols, Unnamed Item, Unnamed Item, Unnamed Item, Sharing the cost of multicast transmissions, Distributed construction of purely additive spanners, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The communication complexity of enumeration, elimination, and selection, Fast Private Norm Estimation and Heavy Hitters, The communication complexity of private simultaneous messages, revisited, On the power of Las Vegas II: Two-way finite automata, Exact OBDD Bounds for Some Fundamental Functions, Approximate proof-labeling schemes, New bounds for energy complexity of Boolean functions, Secure computation of the median (and other elements of specified ranks), Sensing as a Complexity Measure, Rectangles Are Nonnegative Juntas, Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions, Preface, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Optimal Lower Bounds on Regular Expression Size Using Communication Complexity, Parallel Repetition of the Odd Cycle Game, Derandomization for sliding window algorithms with strict correctness, Communication Lower Bounds Via the Chromatic Number, Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity, On pure space vs catalytic space, Superfast coloring in CONGEST via efficient color sampling, Superfast coloring in CONGEST via efficient color sampling, Information complexity of the AND function in the two-party and multi-party settings, The Impact of Locality in the Broadcast Congested Clique Model, Unnamed Item, Unnamed Item, Adventures in monotone complexity and TFNP, The Communication Complexity of Distributed epsilon-Approximations, Lifting Theorems for Equality, Equality alone does not simulate randomness, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Palette-alternating tree codes, Unnamed Item, The Communication Complexity of Set Intersection and Multiple Equality Testing, The complexity of quantum disjointness, Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem, Exponential Separation of Communication and External Information, Distributed Spanner Approximation, Communication Complexity of Pairs of Graph Families with Applications, Unnamed Item, An Additive Combinatorics Approach Relating Rank to Communication Complexity, Communication Lower Bounds Using Directional Derivatives, Communication Complexity of Statistical Distance, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Unnamed Item, Unnamed Item, Unnamed Item, On pure space vs catalytic space, Freezing, Bounded-Change and Convergent Cellular Automata, Introduction to local certification, A linear lower bound on the unbounded error probabilistic communication complexity., On finding common neighborhoods in massive graphs., The rectangle covering number of random Boolean matrices, Communication complexity and linearly ordered sets, Computational hardness of optimal fair computation: beyond Minicrypt, On relations between counting communication complexity classes, Bundling equilibrium in combinatorial auctions, Cellular automata and communication complexity, On multi-partition communication complexity, Comparing the size of NFAs with and without \(\epsilon\)-transitions, Tight lower bounds for query processing on streaming and external memory data, On Slepian-Wolf theorem with interaction, Proof labeling schemes, Upper bounds on the Boolean rank of Kronecker products, Two absolute bounds for distributed bit complexity, The landscape of communication complexity classes, Classical versus quantum communication in XOR games, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, A second look at counting triangles in graph streams (corrected), The (minimum) rank of typical fooling-set matrices, On public-coin zero-error randomized communication complexity, The augmentation property of binary matrices for the binary and Boolean rank, The function-inversion problem: barriers and opportunities, Interval selection in the streaming model, On the monotonicity of a data stream, The Boolean rank of the uniform intersection matrix and a family of its submatrices, Nondeterministic communication complexity with help and graph functions, The communication complexity of graphical games on grid graphs, When distributed computation is communication expensive, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), The unbounded-error communication complexity of symmetric functions, Intractability of min- and max-cut in streaming graphs, Information theoretical cryptogenography, New results on the most significant bit of integer multiplication, Quantum speed-up for unsupervised learning, Fooling sets and the spanning tree polytope, A note on hardness of diameter approximation, On the fastest Vickrey algorithm, Exact OBDD bounds for some fundamental functions, Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs, Communication complexity of approximate maximum matching in the message-passing model, Detecting cliques in CONGEST networks, Fooling views: a new lower bound technique for distributed computations under congestion, Euclidean distance matrices and separations in communication complexity theory, Information complexity and applications., Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors, New applications of the incompressibility method. II, Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds, The hardest halfspace, Non-interactive proofs of proximity, Space-efficient algorithms for longest increasing subsequence, Deciding and verifying network properties locally with few output bits, The direct sum of universal relations, How long to Pareto efficiency?, Property testing lower bounds via a generalization of randomized parity decision trees, Introduction to computer science and economic theory, Randomized proof-labeling schemes, On the power of randomized multicounter machines, On complexity of single-minded auction, On the minimal Hamming weight of a multi-base representation, On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's, Quantum branching programs and space-bounded nonuniform quantum complexity, Redundancy in distributed proofs, Economic efficiency requires interaction, A stable marriage requires communication, Simulation theorems via pseudo-random properties, Placing conditional disclosure of secrets in the communication complexity universe, Distributed monitoring of election winners, Search complexity: a way for the quantitative analysis of the search space, A note on multiparty communication complexity and the Hales-Jewett theorem, Nondeterministic and randomized Boolean hierarchies in communication complexity, Public vs. private randomness in simultaneous multi-party communication complexity, Message lower bounds via efficient network synchronization, Counting the number of perfect matchings, and generalized decision trees, The role of randomness in the broadcast congested clique model, A distributed algorithm for spectral sparsification of graphs with applications to data clustering, Exact communication costs for consensus and leader in a tree, On the relative succinctness of sentential decision diagrams, A counter-example to the probabilistic universal graph conjecture via randomized communication complexity, Communication complexity tools on recognizable picture languages, Resolution over linear equations modulo two, 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, A short proof that the extension complexity of the correlation polytope grows exponentially, Quantum communication and complexity., On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata, Lower bounds for dynamic algebraic problems, Communication complexity method for measuring nondeterminism in finite automata, On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs, Ordered biclique partitions and communication complexity problems, Streaming algorithms for extent problems in high dimensions, Trading information complexity for error. II: The case of a large error and the external information complexity, Fooling-sets and rank, No easy puzzles: hardness results for jigsaw puzzles, Cancellation-free circuits in unbounded and bounded depth, Upper bounds on communication in terms of approximate rank, Proof complexity of symbolic QBF reasoning, On the streaming indistinguishability of a random permutation and a random function, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, Almost optimal query algorithm for hitting set using a subset query, Fine-grained complexity lower bounds for problems in computer aided verification, Inductive definitions in logic versus programs of real-time cellular automata, Lifting query complexity to time-space complexity for two-way finite automata, The communication complexity of functions with large outputs, Energy-efficient distributed algorithms for synchronous networks, Asynchronous communicating cellular automata: formalization, robustness and equivalence, Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols, Bounds on oblivious multiparty quantum communication complexity, On minimally non-firm binary matrices, Error-Free Affine, Unitary, and Probabilistic OBDDs, Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams, Forty years of frequent items, Communication and information complexity, Unnamed Item, Unnamed Item, Distributed Testing of Graph Isomorphism in the CONGEST Model., On the Complexity of the Hidden Weighted Bit Function for Various BDD Models, Communication Complexity and Lower Bounds on Multilective Computations, Finding the Median (Obliviously) with Bounded Space, Query Complexity in Expectation, Unraveling simplicity in elementary cellular automata, On the Power of Learning from k-Wise Queries, Complexity Analysis: Transformation Monoids of Finite Automata, Interactive Information Complexity, Some improved bounds on communication complexity via new decomposition of cliques, The Communication Complexity of Non-signaling Distributions, Communication Lower Bounds via Critical Block Sensitivity, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Individual communication complexity, The Cost of Fault Tolerance in Multi-Party Communication Complexity, Unnamed Item, Unnamed Item, Interactive Information Complexity, Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness, Deterministic Communication vs. Partition Number, Quantifying Communication in Synchronized Languages, Bounds on the number of 2-level polytopes, cones, and configurations, Lower Bounds for Subgraph Detection in the CONGEST Model, Space-Efficient Algorithms for Longest Increasing Subsequence, The Hardness of Being Private, From Quantum Query Complexity to State Complexity, Extended formulations for matroid polytopes through randomized protocols, Equality, Revisited, The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials, Proof-labeling schemes: broadcast, unicast and in between, Menu mechanisms, Enhancing distributed functional monitoring with quantum protocols, On the OBDD Complexity of the Most Significant Bit of Integer Multiplication, Distributed Control of Linear Systems Allowing Choices, Quantum one-way versus classical two-way communication in XOR games, Smallest Formulas for Parity of 2 k Variables Are Essentially Unique, Quantum communication complexity advantage implies violation of a Bell inequality, Privacy in non-private environments, On the OBDD complexity of the most significant bit of integer multiplication, On a Conjecture by Christian Choffrut, Extension Complexity of Independent Set Polytopes, Dimension-free bounds and structural results in communication complexity, On deterministic sketching and streaming for sparse recovery and norm estimation, Generalizations of the distributed Deutsch–Jozsa promise problem, Sign rank versus Vapnik-Chervonenkis dimension, Mechanism design with a restricted action space, The Complexity of Complexity, Optimal collapsing protocol for multiparty pointer jumping, On the communication complexity of approximate Nash equilibria, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, On the Non-deterministic Communication Complexity of Regular Languages, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Strict group testing and the set basis problem, No nonlocal box is universal, The communication requirements of social choice rules and supporting budget sets, Interleaved Group Products, Secret-Sharing Schemes: A Survey, The complexity of fixed point models of trust in distributed networks, Jump Number of Two-Directional Orthogonal Ray Graphs, Lower Bounds for Testing Computability by Small Width OBDDs, Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models, The Hardness of Median in the Synchronized Bit Communication Model, Space Lower Bounds for Online Pattern Matching, On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity, Limitations on Quantum Dimensionality Reduction, Communication complexity of some number theoretic functions, Lower bounds for predecessor searching in the cell probe model, Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions, Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, Non-independent randomized rounding and coloring, Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols, Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits, The communication requirements of efficient allocations and supporting prices, On Toda’s Theorem in Structural Communication Complexity, 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, Larger Lower Bounds on the OBDD Complexity of Integer Multiplication, Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size, Upper and Lower Bounds on the Power of Advice, The Multiparty Communication Complexity of Set Disjointness, The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model, Streaming Algorithms with One-Sided Estimation, Everywhere-Tight Information Cost Tradeoffs for Augmented Index, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, Frequent Directions: Simple and Deterministic Matrix Sketching, Trading Bit, Message, and Time Complexity of Distributed Algorithms, The Complexity of Data Aggregation in Directed Networks, $$P\mathop{ =}\limits^{?}NP$$, Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs, Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems, Fooling Pairs in Randomized Communication Complexity, Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity, Message Lower Bounds via Efficient Network Synchronization, Unnamed Item, Unnamed Item, Unnamed Item, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), On the influence of the variable ordering for algorithmic learning using OBDDs, Construction of Very Hard Functions for Multiparty Communication Complexity, On maximal isolation sets in the uniform intersection matrix
