Skip to main content

We gratefully acknowledge support from
the Simons Foundation and member institutions.
arXiv.org > cs > arXiv:1611.08842
Help | Advanced Search
All fields
Title
Author
Abstract
Comments
Journal reference
ACM classification
MSC classification
Report number
arXiv identifier
DOI
ORCID
arXiv author ID
Help pages
Full text
Search
Computer Science > Computational Complexity
[Submitted on 27 Nov 2016 (v1), last revised 31 Aug 2020 (this version, v3)]
The communication complexity of the inevitable intersection problem
Dmitry Gavinsky
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including $-$ most famously $-$ interactive randomised communication with bounded error, the problem requires much communication.
In this work we were looking for a variation of the set disjointness problem, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection.
Subjects:
Computational Complexity (cs.CC)
Cite as:
arXiv:1611.08842 [cs.CC]
(or arXiv:1611.08842v3 [cs.CC] for this version)
Submission history
From: Dmitry Gavinsky [view email]
[v1] Sun, 27 Nov 2016 13:47:16 UTC (15 KB)
[v2] Sun, 21 May 2017 00:54:02 UTC (13 KB)
[v3] Mon, 31 Aug 2020 01:28:48 UTC (17 KB)
Download:
• PDF
• PostScript
• Other formats
(license)
Current browse context:
cs.CC
< prev | next >
new | recent | 1611
Change to browse by:
cs
References & Citations
• NASA ADS
• Google Scholar
• Semantic Scholar
DBLP – CS Bibliography
listing | bibtex
Dmitry Gavinsky
Export Bibtex Citation
Bookmark
   
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Code
Related Papers
About arXivLabs
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)
About
Help
contact arXivClick here to contact arXiv
Contact
subscribe to arXiv mailingsClick here to subscribe
Subscribe
Copyright
Privacy Policy
Web Accessibility Assistance
arXiv Operational Status
Get status notifications via email or slack