Communication Complexity
From MaRDI portal
Publication:4875692
Recommendations
Cited in
(only showing first 100 items - show all)- Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions
- 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
- New results for finding common neighborhoods in massive graphs in the data stream model
- Property testing of the Boolean and binary rank
- Communication complexity of statistical distance
- 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
- The hardest halfspace
- Communication complexity tools on recognizable picture languages
- Deciding and verifying network properties locally with few output bits
- On the influence of the variable ordering for algorithmic learning using OBDDs
- How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
- The Communication Complexity of Non-signaling Distributions
- On biclique covering number of the Cartesian product of graphs
- The complexity of quantum disjointness
- On the complexity of communication complexity
- On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
- The layer complexity of Arthur-Merlin-like communication
- On the relative succinctness of sentential decision diagrams
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- scientific article; zbMATH DE number 7250148 (Why is no real title available?)
- On the expressive power of CNF formulas of bounded tree- and clique-width
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- A second look at counting triangles in graph streams (corrected)
- Introduction to local certification
- Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
- One-way multiparty communication lower bound for pointer jumping with applications
- Best-order streaming model
- Kolmogorov complexity and combinatorial methods in communication complexity
- On Toda’s Theorem in Structural Communication Complexity
- Ordered biclique partitions and communication complexity problems
- The (minimum) rank of typical fooling-set matrices
- Communication complexity of pairs of graph families with applications
- On public-coin zero-error randomized communication complexity
- Trading information complexity for error. II: The case of a large error and the external information complexity
- STACS 2004
- New results on the most significant bit of integer multiplication
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- A note on efficient aggregate queries in sensor networks
- New bounds on the half-duplex communication complexity
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Communication complexity and linearly ordered sets
- Palette-alternating tree codes
- Clique versus independent set
- A note on randomized mutual search.
- Lower bounds for linearly transformed OBDDs and FBDDs
- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
- Approximate proof-labeling schemes
- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Euclidean distance matrices and separations in communication complexity theory
- Information complexity and applications.
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- The communication complexity of the Hamming distance problem
- Exact OBDD bounds for some fundamental functions
- On cover-structure graphs
- The navigational power of web browsers
- Extremal problems under dimension constraints.
- Fooling views: a new lower bound technique for distributed computations under congestion
- Communication complexity of approximate maximum matching in the message-passing model
- Experimental multipartner quantum communication complexity employing just one qubit
- Implausible consequences of superstrong nonlocality
- Separating OR, SUM, and XOR circuits
- Equality alone does not simulate randomness
- Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
- The Complexity of Complexity
- Jump number of two-directional orthogonal ray graphs
- Computational hardness of optimal fair computation: beyond Minicrypt
- Partition arguments in multiparty communication complexity
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Lifting query complexity to time-space complexity for two-way finite automata
- Complexity Analysis: Transformation Monoids of Finite Automata
- Exact OBDD Bounds for Some Fundamental Functions
- Communication complexity and intrinsic universality in cellular automata
- Multiparty communication complexity and very hard functions
- Equality, revisited
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- From quantum query complexity to state complexity
- Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
- Property testing lower bounds via a generalization of randomized parity decision trees
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Linear algebraic methods in communication complexity
- Dimension-free bounds and structural results in communication complexity
- Some improved bounds on communication complexity via new decomposition of cliques
- On the parity complexity measures of Boolean functions
- Smallest formulas for the parity of \(2^k\) variables are essentially unique
- On the minimal Hamming weight of a multi-base representation
- An additive combinatorics approach relating rank to communication complexity
- Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
- A characterization of average case communication complexity
- The augmentation property of binary matrices for the binary and Boolean rank
- Construction of Very Hard Functions for Multiparty Communication Complexity
- Space-bounded communication complexity
- On probabilistic pushdown automata
- Unbounded-Error Classical and Quantum Communication Complexity
- Energy-efficient distributed algorithms for synchronous networks
- The communication complexity of functions with large outputs
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)
