Can Many Instances Be Cheaper Than One? The Price of Agreement in EliminationResearch Paper
Direct-sum and direct-product questions ask how the cost of solving independent instances of a communication problem relates to the cost of one. Elimination asks for much less than computing: given instances, the parties only have to output some answer vector that is not the true one. Guessing a uniformly random already errs…