License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.7
URN: urn:nbn:de:0030-drops-115036
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11503/
Goldstein, Isaac ;
Lewenstein, Moshe ;
Porat, Ely
On the Hardness of Set Disjointness and Set Intersection with Bounded Universe
Abstract
In the SetDisjointness problem, a collection of m sets S_1,S_2,...,S_m from some universe U is preprocessed in order to answer queries on the emptiness of the intersection of some two query sets from the collection. In the SetIntersection variant, all the elements in the intersection of the query sets are required to be reported. These are two fundamental problems that were considered in several papers from both the upper bound and lower bound perspective.
Several conditional lower bounds for these problems were proven for the tradeoff between preprocessing and query time or the tradeoff between space and query time. Moreover, there are several unconditional hardness results for these problems in some specific computational models. The fundamental nature of the SetDisjointness and SetIntersection problems makes them useful for proving the conditional hardness of other problems from various areas. However, the universe of the elements in the sets may be very large, which may cause the reduction to some other problems to be inefficient and therefore it is not useful for proving their conditional hardness.
In this paper, we prove the conditional hardness of SetDisjointness and SetIntersection with bounded universe. This conditional hardness is shown for both the interplay between preprocessing and query time and the interplay between space and query time. Moreover, we present several applications of these new conditional lower bounds. These applications demonstrates the strength of our new conditional lower bounds as they exploit the limited universe size. We believe that this new framework of conditional lower bounds with bounded universe can be useful for further significant applications.
BibTeX - Entry
@InProceedings{goldstein_et_al:LIPIcs:2019:11503,
author = {Isaac Goldstein and Moshe Lewenstein and Ely Porat},
title = {{On the Hardness of Set Disjointness and Set Intersection with Bounded Universe}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {7:1--7:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11503},
URN = {urn:nbn:de:0030-drops-115036},
doi = {10.4230/LIPIcs.ISAAC.2019.7},
annote = {Keywords: set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds}
}
|
Keywords: |
|
set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
