More Like this

1. Tight Bounds for Monotone Minimal Perfect Hashing

   https://doi.org/10.1145/3677608  

   Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (October 2025, ACM Transactions on Algorithms)

   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
2. Sketching Approximability of All Finite CSPs

   https://doi.org/10.1145/3649435  

   Chou, Chi-Ning; Golovnev, Alexander; Sudan, Madhu; Velusamy, Santhoshini (April 2024, Journal of the ACM)

   A constraint satisfaction problem (CSP),\(\textsf {Max-CSP}(\mathcal {F})\), is specified by a finite set of constraints\(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\)for positive integersqandk. An instance of the problem onnvariables is given bymapplications of constraints from\(\mathcal {F}\)to subsequences of thenvariables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family\(\mathcal {F}\)and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in\(o(\sqrt {n})\)space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case ofq=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of\(\mathcal {F}\)support a distribution on\([q]^k\)with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variablesq= 2, binary constraintsk=2, and singleton families\(|\mathcal {F}|=1\)and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [56], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to generalq-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes. 

   more » « less
3. Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median

   https://doi.org/10.1145/3817044  

   Gowda, Kishen N; Pensyl, Thomas; Srinivasan, Aravind; Trinh, Khoa (May 2026, ACM Transactions on Probabilistic Machine Learning)

   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
4. Tiny Pointers

   https://doi.org/10.1145/3700594  

   Bender, Michael A; Conway, Alex; Farach-Colton, Martín; Kuszmaul, William; Tagliavini, Guido (October 2024, ACM Transactions on Algorithms)

   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
5. Node-Differentially Private Estimation of the Number of Connected Components

   https://doi.org/10.1145/3762664  

   Kalemaj, Iden; Raskhodnikova, Sofya; Smith, Adam; Tsourakakis, Charalampos (January 2026, ACM Transactions on Algorithms)

   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