@booklet {yannaiagonczarowski-asmrc2014,
	title = {A Stable Marriage Requires Communication},
	howpublished = {Discussion Papers},
	year = {2014},
	month = {6},
	abstract = {The Gale-Shapely algorithm for the Stable Marriage Problem is known to take Theta(n^2) steps to find a stable marriage in the worst case, but only Theta(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that Theta(n^2) queries are required in a model that allows certain natural random-access queries to the participants{\textquoteright} preferences. Using a reduction to the communication complexity of the disjointness problem, we prove a significantly more general - albeit slightly weaker - result, showing that Omega(n^2) Boolean queries of any type are required. Our lower bound generalizes to (A) randomized algorithms, (B) even just verifying the stability of a proposed marriage, (C) even allowing arbitrary separate preprocessing of the women{\textquoteright}s preferences and of the men{\textquoteright}s preferences, and (D) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.},
	url = {/files/dp667.pdf},
	author = {Yannai A. Gonczarowski, Noam Nisan}
}
