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

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

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length t proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string x is Kolmogorov random (x{\in}R) is ... more >>>