Vikraman Arvind, Jacobo Toran

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

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

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