We study robust mechanism design for revenue maximization when selling a single item in an auction, assuming that only the mean of the value distribution and an upper bound on the bidders' valuations for the item are known. Robust mechanism design is a rising alternative to Bayesian mechanism design, which yields designs that do not rely on assumptions like full distributional knowledge, but rather only partial knowledge of the distributions. We seek a mechanism that maximizes revenue over the worst-case distribution compatible with the known parameters. Such a mechanism arises as an equilibrium of a zero-sum game between the seller and an adversary who chooses the distribution, and so can be referred to as the max-min mechanism.

This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing tildeΩmega (n2) lower bounds for cornerstone problems, such as minimum dominating set (MDS), Hamiltonian path, Steiner tree and max-cut. These are almost tight, since all of these problems can be solved optimally in O(n2) rounds. Moreover, we show that even in bounded-degree graphs and even in simple graphs with maximum degree 5 and logarithmic diameter, it holds that various tasks, such as finding a maximum independent set (MaxIS) or a minimum vertex cover, are still difficult, requiring a near-tight number of tildeΩ (n) rounds.