On the distributional complexity of disjointness

DOI10.1016/0304-3975(92)90260-MzbMath0787.68055MaRDI QIDQ1202933

Alexander A. Razborov

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

communication complexity

Mathematics Subject Classification ID

Related Items (99)

The corruption bound, log-rank, and communication complexity ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Interactive Information Complexity ⋮ Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Memory lower bounds of reductions revisited ⋮ Anchored Parallel Repetition for Nonlocal Games ⋮ The landscape of communication complexity classes ⋮ Interactive Information Complexity ⋮ On rank vs. communication complexity ⋮ Common information and unique disjointness ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Certifying equality with limited interaction ⋮ A discrepancy lower bound for information complexity ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Explicit exponential lower bounds for exact hyperplane covers ⋮ An information statistics approach to data stream and communication complexity ⋮ Fourier analysis for probabilistic communication complexity ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Communication complexity with small advantage ⋮ Distributed Testing of Distance-k Colorings ⋮ Around the log-rank conjecture ⋮ Communication costs in a geometric communication network ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Secure sampling with sublinear communication ⋮ The communication complexity of functions with large outputs ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Query-to-Communication Lifting for BPP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on hardness of diameter approximation ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ On a theorem of Razborov ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Information complexity and applications. ⋮ Quantum lower bounds by quantum arguments ⋮ String Matching: Communication, Circuits, and Learning. ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ On the power of randomized multicounter machines ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On probabilistic pushdown automata ⋮ A stable marriage requires communication ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Unnamed Item ⋮ 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 ⋮ Rectangles Are Nonnegative Juntas ⋮ Exponential separation of quantum and classical online space complexity ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Message lower bounds via efficient network synchronization ⋮ Sketching information divergences ⋮ Extended formulations, nonnegative factorizations, and randomized communication protocols ⋮ On the extension complexity of combinatorial polytopes ⋮ Information complexity of the AND function in the two-party and multi-party settings ⋮ Upper and Lower Bounds on the Power of Advice ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item ⋮ On the Communication Complexity of Key-Agreement Protocols. ⋮ The Complexity of Data Aggregation in Directed Networks ⋮ Unnamed Item ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ New bounds on classical and quantum one-way communication complexity ⋮ Testing computability by width-two OBDDs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Pointer chasing via triangular discrimination ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ The complexity of quantum disjointness ⋮ Exponential Separation of Communication and External Information ⋮ Distributed Spanner Approximation ⋮ On the P versus NP intersected with co-NP question in communication complexity ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially ⋮ Quantum communication and complexity. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Upper bounds on communication in terms of approximate rank ⋮ On the streaming indistinguishability of a random permutation and a random function

This page was built for publication: On the distributional complexity of disjointness