notesum.ai

Published at November 28

Hashing for Sampling-Based Estimation

cs.DS

Released Date: November 28, 2024

Authors: Anders Aamand¹, Ioana O. Bercea², Jakob Bæk Tejs Houen³, Jonas Klausen¹, Mikkel Thorup¹

Aff.: ¹University of Copenhagen; ²Kungliga Tekniska Högskolan; ³Alipes ApS

Arxiv: http://arxiv.org/pdf/2411.19394v1

Symbol	Definition	Description
$s_{sec}$	$20$	Scales error probability of secondary events
$s_{all}$	160	Scales error probability in each layer
$p_{reg}$	$\frac{p}{\log_{6}\left(\frac{\mu/2}{\ln(s_{sec}/p)}\right)}\cdot\frac{1}{s_{% all}}$	Threshold for error probability in regular layers
$i_{nr}$	$\min\left\{i:\bar{\mu}_{i}<\ln(s_{all}/p_{reg})\right\}$	First non-regular layer
$i_{\max}$	$\ln(\|\Sigma\|^{d-2}2^{s})$	Maximum number of layers with non-zero expected size (whp), where $s$ is the number of selection bits. Defined in Lemma 16.
$n_{top}$	$\log_{6}(\ln(s_{sec}/p_{reg})\cdot s_{all}/p)$	Bound on the number of layers handled by Lemma 27
$p_{top}$	$\min\left\{\frac{p_{reg}}{s_{sec}},\,\frac{p}{n_{top}\cdot s_{all}}\right\}$	Error probability for each layer in Lemma 27
$\varepsilon_{3}$	$(2+\sqrt{6})\sqrt{\ln(s_{sec}/p)/\|\Sigma\|}+(\frac{1}{2}\ln(1/p)+6)/\mu$	Stretch factor of multiplicative deviation of Theorem 12
$\Delta_{reg}$	$0.181\sqrt{\ln(1/p)\mu}+0.066\sqrt{\frac{\mu}{\ln(1/p)}}+\sqrt{2}$	Total deviation of regular layers, from 4 and up (Theorem 14)
$\Delta_{i_{nr}}$	$1.33e\ln(s_{sec}/p_{reg})+1$	Deviation of layer $i_{nr}$ (Lemma 25)
$\Delta_{top}$	$2\ln(1/p_{top})\cdot(2+\ln\ln(n_{top}))+n_{top}$	Deviation of layers $i_{nr}+1$ through $i_{\infty}$ (Lemma 27)
$\Delta_{nonreg}$	$\Delta_{i_{nr}}+\Delta_{top}+3$	Total deviation of non-regular layers, $i_{nr}$ and above (Theorem 15)
$\gamma_{1}$	$\sqrt{7/3\cdot(1+\varepsilon_{3})}+0.181$	Multiplicative term of deviation in Theorem 35
$\gamma_{2}$	$\Delta_{reg}-0.181\sqrt{\ln(1/p)\mu}+\Delta_{nonreg}+\ln(1/p)$	Additive term of deviation in Theorem 35