A strong direct product theorem for disjointness
From MaRDI portal
Publication:2875134
DOI10.1145/1806689.1806702zbMath1293.68146OpenAlexW2042753471WikidataQ58040207 ScholiaQ58040207MaRDI QIDQ2875134
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806702
lower boundscommunication complexitycomplexity theorydirect product theoremsdisjointness problemcommunication-space tradeoffs
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Interactive Information Complexity, The landscape of communication complexity classes, Interactive Information 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, A discrepancy lower bound for information complexity, Unnamed Item, From private simultaneous messages to zero-information Arthur-Merlin protocols and back, A monogamy-of-entanglement game with applications to device-independent quantum cryptography, Improved direct product theorems for randomized query complexity, Unnamed Item, New Strong Direct Product Results in Communication Complexity, From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back, Rectangles Are Nonnegative Juntas, Upper and Lower Bounds on the Power of Advice, The Multiparty Communication Complexity of Set Disjointness, Query-To-Communication Lifting for BPP Using Inner Product, The Communication Complexity of Set Intersection and Multiple Equality Testing, The complexity of quantum disjointness, Communication Lower Bounds Using Directional Derivatives, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Unnamed Item
