Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sparse sets:
TR98-027 | 15th April 1998
Vikraman Arvind, Jacobo Toran

Sparse sets, approximable sets, and parallel queries to NP

We relate the existence of disjunctive hard sets for NP to
other well studied hypotheses in complexity theory showing
that if an NP-complete set or a coNP-complete set is
polynomial-time disjunctively reducible
to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using
a similar argument we obtain also that ... more >>>

TR20-114 | 22nd July 2020
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

ISSN 1433-8092 | Imprint