An official website of the United States government
This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional\(\log n\)-bit pointers can be replaced with\(o(\log n)\)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor\(1-\delta\), then the optimal tiny-pointer size is\(\Theta(\log\log\log n+\log\delta^{-1})\)bits in the fixed-size case, and\(\Theta(\log\delta^{-1})\)expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that:A data structure storing\(n\)\(v\)-bit values for\(n\)keys with constant-factor time modifications/queries can be implemented to take space\(nv+O(n\log^{(r)}n)\)bits, for any constant\(r\gt0\), as long as the user stores a tiny pointer of expected size\(O(1)\)with each key—here,\(\log^{(r)}n\)is the\(r\)-th iterated logarithm.Any binary search tree can be made succinct, meaning that it achieves\((1+o(1))\)times the optimal space, with constant-factor time overhead, and can even be made to be within\(O(n)\)bits of optimal if we allow for\(O(\log^{*}n)\)-time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree.Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and\((1+o(1))\)-factor space overhead.Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of\(\log^{(r)}n+O(\log j)\)bits per\(j\)-bit value for an arbitrary constant\(r\gt0\)of our choice.Given an external-memory array\(A\)of size\((1+\varepsilon)n\)containing a dynamic set of up to\(n\)key-value pairs, it is possible to maintain an internal-memory stash of size\(O(n\log\varepsilon^{-1})\)bits so that the location of any key-value pair in\(A\)can be computed in constant time (and with no IOs). In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.
more »
« less
This content will become publicly available on May 23, 2027
Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median
The metric\(k\)-median problem is a classical and widely studied objective for data clustering, with applications in data analysis, computer vision, genomics, and facility location. The current best approximation algorithms for\(k\)-median rely on first obtaining a structured fractional solution known as abi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-discretized partitioning schemes for the facilities, along with corresponding sets of randomized algorithms and factor-revealing non-linear programs. We show this hierarchy improves upon the current best factor of\(1.3371\), proving that the third layer of this hierarchy achieves a rounding factor of\(1.3064\), while no layer can achieve a factor smaller than\(1.2943\)in expectation. Combined with the current best algorithm for bi-point solution generation, we get a\(2.6081\)approximation factor for\(k\)-median. On the negative side, we give a family of bi-point solutions with integrality gap approaching the square root of the golden ratio, approximately\(1.272\), even when allowed to open\(k+o(k)\)facilities. Altogether, our results substantially narrow the approximation gap for bi-point solutions.
more »
« less
- Award ID(s):
- 2317194
- PAR ID:
- 10694069
- Publisher / Repository:
- ACM Transactions on Probabilistic Machine Learning
- Date Published:
- Journal Name:
- ACM Transactions on Probabilistic Machine Learning
- ISSN:
- 2836-8924
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Themonotone minimal perfect hash function(MMPHF)problem is the following indexing problem. Given a set\(S=\{s_{1},\ldots,s_{n}\}\)of\(n\)distinct keys from a universe\(U\)of size\(u\), create a data structure\(\mathbf{D}\)that answers the following query:\(\rm{{R\small{ANK}}}(q)=\begin{cases}\text{rank of }q\text{ in }S&q\in S \\ \text{arbitrary answer}&\text{otherwise.}\end{cases}\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes\(\mathbf{D}\)in\(O(n\log\log\log u)\)bits and performs queries in\(O(\log u)\)time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this article, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of\(n\)elements from a universe of size\(u\)requires\(\Omega(n\cdot\log\log\log{u})\)expected bits to answer every query correctly. We achieve our lower bound by defining a graph\(\mathbf{G}\)where the nodes are the possible\({u\choose n}\)inputs and where two nodes are adjacent if they cannot share the same\(\mathbf{D}\). The size of\(\mathbf{D}\)is then lower bounded by the log of the chromatic number of\(\mathbf{G}\). Finally, we show that the fractional chromatic number (and hence the chromatic number) of\(\mathbf{G}\)is lower bounded by\(2^{\Omega(n\log\log\log u)}\).more » « less
-
Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Suppose there exists any set of constants\(\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)\)such that the sub-exponential security of the following assumptions hold:—the Learning With Errors (\(\mathsf {LWE}\)) assumption with subexponential modulus-to-noise ratio\(2^{k^\epsilon }\)and noises of magnitude polynomial ink, wherekis the dimension of the\(\mathsf {LWE}\)secret,—the Learning Parity with Noise (\(\mathsf {LPN}\)) assumption over general prime fields\(\mathbb {Z}_p\)with polynomially many\(\mathsf {LPN}\)samples and error rate\(1/\ell ^\delta\), where\(\ell\)is the dimension of the\(\mathsf {LPN}\)secret,—the existence of a Boolean Pseudo-Random Generator (\(\mathsf {PRG}\)) in\(\mathsf {NC}^0\)with stretch\(n^{1+\tau }\), wherenis the length of the\(\mathsf {PRG}\)seed,—the Decision Linear (\(\mathsf {DLIN}\)) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Furthermore, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.more » « less
-
We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an\( n \)-vertex graph\( G \)and a privacy parameter\(\varepsilon\), our algorithm runs in polynomial time and, with probability\(1-o(1)\), has additive error\(\widetilde{O}(\frac{\Delta^{*}\ln\ln n}{\varepsilon}),\)where\(\Delta^{*}\)is the smallest possible maximum degree of a spanning forest of\(G.\)Node-differentially private algorithms are known only for a small number of database analysis tasks. A major obstacle for designing such an algorithm for the number of connected components is that this graph statistic is not robust to adding one node with arbitrary connections (a change that node-differential privacy is designed to hide):everygraph is a neighbor of a connected graph. We overcome this by designing a family of efficiently computable Lipschitz extensions of the number of connected components or, equivalently, the size of a spanning forest. The construction of the extensions, which is at the core of our algorithm, is based on the forest polytope of\(G.\)We prove several combinatorial facts about spanning forests, in particular, that a graph with no induced\(\Delta\)-stars has a spanning forest of degree at most\(\Delta\). With this fact, we show that our Lipschitz extensions for the number of connected components equal the true value of the function for the largest possible monotone families of graphs. More generally, on all monotone sets of graphs, the\(\ell_{\infty}\)error of our Lipschitz extensions is nearly optimal.more » « less
