It is proved that the expected insertion time of the hash table is $\epsilon^{-(1 + o(1))}$.
Abstract
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the form $f(\epsilon^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $\epsilon^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $\epsilon^{-1}$.
This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected insertion and query time, as a function of the load factor $1 - \epsilon$? We prove that the \emph{greedy two-choice insertion strategy} ac...
Amir Azarmehr, Michael A. Bender, William Kuszmaul et al.· 0 citations
For a finite set $S$ of positive integers, put $K(S):=-\min_{x\in\mathbb T}\sum_{s\in S}\cos(2\pi sx)$. Bedert recently proved the uniform lower bound $K(S)\geq |S|^{1/5-o(1)}$. We remove the subpolynomial loss and prove that $K(S)\geq c|S|^{1/5}$ for an absolute constant $c>0$. The proof combines two estimates from Be...
Four decades on, H{\aa}stad's classical $2^{\Omega(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are...
Victor Lecomte, Prasanna Ramakrishnan· 0 citations
Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{OneEnd}$ problem asks for a non-scalar endomorphism of $E$. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent $1/3$ under an assumption on the factorization...
An equivalence between the maximum load problem to a density variant of arithmetic Kakeya sets and the classical multiply-shift hash family of Dietzfelbinger, Hagerup, Katajainen, and Penttonen is made.
Following Erd\H{o}s (1982) and Sanna (2019), we study the arithmetic function $h(n)$, which is defined to be the number of distinct exponents in the prime factorization of a positive integer $n$. Among other things, we show that $$ \sum_{n\leq x}h(\phi(n)) \asymp x\left(\frac{\log\log x}{\log\log\log x}\right)^{1/2}, $...
Mikhail R. Gabdullin, V. V. Iudelevich· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
