<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound</title></titleStmt>
			<publicationStmt>
				<publisher>ACM</publisher>
				<date>06/09/2026</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10698362</idno>
					<idno type="doi">10.1145/3798129.3800823</idno>
					
					<author>Martín Farach-Colton</author><author>Andrew Krapivin</author><author>William Kuszmaul</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to $1 - \epsilon$ full, must incur an amortized expected query time of at least $\Omega(\log \epsilon^{-1})$. To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of $O(1).$ The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to $O(\log \epsilon^{-1})$. Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter $\epsilon$ beforehand.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body><div/></body></text>
</TEI>
