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}$.
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...
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...
Let $D(N)$ denote the largest cardinality of a subset of $\{1,\ldots,N\}$ containing no nonzero square difference. While a construction certifying $D(N)\geq (1-o(1))N^{1/2}$ is almost trivial, Erd\H{o}s conjectured that this bound is sharp up to polylogarithmic factors. This was disproved by S\'ark\"ozy and later again...
Consider the canonical universal hash family $h(x)= ((ax+b)\text{ mod } p)\text{ mod } m$, where $a,b$ are chosen uniformly from $\mathbb Z_p$, which we call linear hashing, being used to hash $n$ elements into $m=\Theta(n)$ buckets. For any universal family, the expected size of the largest bucket is at least $\Omega(...
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
A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS'26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured...
Yan Zhong· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
