More Like this

1. Computing a Fixed Point of Contraction Maps in Polynomial Queries

   https://doi.org/10.1145/3744738  

   Chen, Xi; Li, Yuhao; Yannakakis, Mihalis (August 2025, Journal of the ACM)

   We give an algorithm for finding an ε-fixed point of a contraction mapf: [0, 1]^k\(\mapsto\)[0, 1]^kunder the\(\ell _\infty\)-norm with query complexityO(klog (1/ε). 

   more » « less
2. Indistinguishability Obfuscation from Well-Founded Assumptions

   https://doi.org/10.1145/3785007  

   Jain, Aayush; Lin, Huijia; Sahai, Amit (February 2026, Journal of the ACM)

   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
3. 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
4. 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
5. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

   https://doi.org/10.1145/3593809  

   Jambulapati, Arun; Sidford, Aaron (February 2024, ACM Transactions on Algorithms)

   In this paper we provide anO(mloglog^O(1)nlog (1/ϵ))-expected time algorithm for solving Laplacian systems onn-nodem-edge graphs, improving upon the previous best expected runtime of\(O(m \sqrt {\log n} \mathrm{log log}^{O(1)} n \log (1/\epsilon)) \)achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of low spectral stretch graph approximations with improved stretch and sparsity bounds. As motivation for this work, we show that for every set of vectors in\(\mathbb {R}^d \)(not just those induced by graphs) and all integerk> 1 there exist an ultra-sparsifier withd− 1 +O(d/k) re-weighted vectors of relative condition number at mostk². For smallk, this improves upon the previous best known multiplicative factor of\(k \cdot \tilde{O}(\log d) \), which is only known for the graph case. Additionally, in the graph case we employ our low-stretch subgraph construction to obtainn− 1 +O(n/k)-edge ultrasparsifiers of relative condition numberk^{1 +o(1)}fork=ω(log ^δn) for anyδ> 0: this improves upon the previous work fork=o(exp (log ^{1/2 −δ}n)). 

   more » « less