[SOLVED] CS Skip to main content

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?)

AboutHelp
contact arXivClick here to contact arXivContactsubscribe to arXiv mailingsClick here to subscribeSubscribe
CopyrightPrivacy Policy
Web Accessibility AssistancearXiv Operational Status Get status notifications via email or slack