Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2608.23350v1 Announce Type: new Abstract: In this brief note, we close the asymptotic gap between known upper and lower bounds for fractional online matching under edge arrivals. We prove that the optimal…
arXiv:2608.22185v1 Announce Type: cross Abstract: In many practical deployments of differential privacy, queries do not arrive all at once. We study online differentially private query answering under a finite…
arXiv:2608.21562v1 Announce Type: cross Abstract: We show that border rank is equal to rank for Kruskal tensors. We also give an analogous Kruskal condition for alternating tensors, which certifies uniqueness of skew…
arXiv:2511.21637v2 Announce Type: replace-cross Abstract: This paper unifies two foundational constructs from economics and algorithmic game theory, the Arctic Auction and the linear Fisher market, to address the…
arXiv:2608.21987v1 Announce Type: new Abstract: A longstanding limitation of known techniques for parallel derandomization was that they incurred at least polylogarithmic overhead in work. For instance, for fundamental…
arXiv:2608.22488v1 Announce Type: new Abstract: Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric…
arXiv:2608.21594v1 Announce Type: new Abstract: We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm…
arXiv:2112.03738v3 Announce Type: replace Abstract: We provide a more efficient algorithm for computing the Rand Index when the data clusters come from a change-point detection problem. Given the number of data points…
arXiv:2608.22769v1 Announce Type: cross Abstract: We study spectral density estimation for the normalized adjacency matrix of an unweighted graph under local access model. Previously, Cohen-Steiner et al. [KDD 2018]…
arXiv:2602.13106v2 Announce Type: replace-cross Abstract: In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often…
arXiv:2608.22870v1 Announce Type: cross Abstract: A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result…
arXiv:2608.20018v2 Announce Type: replace Abstract: In the Shortest Common Superstring (SCS) problem, one is given a set of strings and is asked to find a string of minimum length containing each of the input strings as…
arXiv:2503.08863v3 Announce Type: replace-cross Abstract: We study two fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), and 3D Minimum Volume Bounding Box (3D-MVBB),…
arXiv:2608.12946v2 Announce Type: replace-cross Abstract: We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using…
arXiv:2608.21932v1 Announce Type: new Abstract: We present an algorithm with a natural geometric interpretation for computing the determinant of a matrix $B\in\mathbb{Z}^{d\times d}$. It improves upon the current…
arXiv:2608.21912v1 Announce Type: new Abstract: Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p+q-d$ with periods $p$ and $q$ also has period $d=\gcd(p,q)$. For parameterized…
arXiv:2608.22671v1 Announce Type: cross Abstract: The uniform car-parking process is the one-dimensional random sequential adsorption of unit cars on a segment of finite length $s$: cars arrive at uniformly random…
arXiv:2608.22355v1 Announce Type: new Abstract: The 3SUM problem asks, given sets $A,B,C$ of integers, whether there exist $a\in A$ and $b\in B$ whose sum belongs to $C$. In the preprocessed variant with unknown $C$,…
arXiv:2502.03696v2 Announce Type: replace Abstract: Recent studies have demonstrated that learned Bloom filters (LBFs), which combine machine learning with the classical Bloom filter, can achieve superior memory…
arXiv:2606.31030v2 Announce Type: replace Abstract: Contextual pattern matching is the task of, given a pattern $P[1,m]$, a context length $\lambda$, and a text $T[1,n]$, find all the $occ$ distinct contexts in which…
Showing 1 day · 56 items available
