Recommendations
Cited in
(only showing first 100 items - show all)- A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
- Informational requirements of social choice rules
- A note on monotone complexity and the rank of matrices
- On the guessing number of shift graphs
- New bounds on classical and quantum one-way communication complexity
- On the P versus NP intersected with co-NP question in communication complexity
- Communication complexity
- Communication complexity of multi-processor systems
- A three-party communication problem
- 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.
- Extremal problems under dimension constraints.
- Recognition problems and communication complexity.
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- BDDs -- design, analysis, complexity, and applications.
- Algorithmic complexity of recursive and inductive algorithms
- Protocols for asymmetric communication channels
- A note on randomized mutual search.
- Lower bounds for linearly transformed OBDDs and FBDDs
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- The corruption bound, log-rank, and communication complexity
- An adaptivity hierarchy theorem for property testing
- On Slepian-Wolf theorem with interaction
- The landscape of communication complexity classes
- Classical versus quantum communication in XOR games
- The augmentation property of binary matrices for the binary and Boolean rank
- On the monotonicity of a data stream
- Information theoretical cryptogenography
- Fooling sets and the spanning tree polytope
- A note on hardness of diameter approximation
- Euclidean distance matrices and separations in communication complexity theory
- Information complexity and applications.
- Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
- Non-interactive proofs of proximity
- The direct sum of universal relations
- On the power of randomized multicounter machines
- On complexity of single-minded auction
- Quantum branching programs and space-bounded nonuniform quantum complexity
- A note on multiparty communication complexity and the Hales-Jewett theorem
- Exact communication costs for consensus and leader in a tree
- 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
- A linear lower bound on the unbounded error probabilistic communication complexity.
- On finding common neighborhoods in massive graphs.
- On relations between counting communication complexity classes
- Bundling equilibrium in combinatorial auctions
- Cellular automata and communication complexity
- On multi-partition communication complexity
- Intractability of min- and max-cut in streaming graphs
- Quantum speed-up for unsupervised learning
- On the fastest Vickrey algorithm
- Exact OBDD bounds for some fundamental functions
- New applications of the incompressibility method. II
- The hardest halfspace
- Space-efficient algorithms for longest increasing subsequence
- Deciding and verifying network properties locally with few output bits
- Property testing lower bounds via a generalization of randomized parity decision trees
- Randomized proof-labeling schemes
- On the minimal Hamming weight of a multi-base representation
- Redundancy in distributed proofs
- Placing conditional disclosure of secrets in the communication complexity universe
- Search complexity: a way for the quantitative analysis of the search space
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- 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
- A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
- 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
- Trading information complexity for error. II: The case of a large error and the external information complexity
- 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
- Computational hardness of optimal fair computation: beyond Minicrypt
- Upper bounds on the Boolean rank of Kronecker products
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- On public-coin zero-error randomized communication complexity
- The function-inversion problem: barriers and opportunities
- The communication complexity of graphical games on grid graphs
- 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
- Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors
- How long to Pareto efficiency?
- Introduction to computer science and economic theory
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Economic efficiency requires interaction
- A stable marriage requires communication
- Simulation theorems via pseudo-random properties
- Distributed monitoring of election winners
- Public vs. private randomness in simultaneous multi-party communication complexity
- Message lower bounds via efficient network synchronization
- On the relative succinctness of sentential decision diagrams
- Communication complexity tools on recognizable picture languages
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)
