Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
67 articles · 3 sources · 67 papers ·
Top topics: Algorithms · AI · Information Retrieval
arXiv:2610.16045v2 Announce Type: replace Abstract: Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $\Theta(\log k)$,…
arXiv:2610.41723v1 Announce Type: cross Abstract: Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small. This…
arXiv:2610.41620v1 Announce Type: new Abstract: A class of graphs $\mathcal{G}$ is tame if there is a constant c such that every $n$-vertex graph in $\mathcal{G}$ has at most $n^c$ minimal separators. Many important…
arXiv:2609.30215v2 Announce Type: replace Abstract: We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For…
arXiv:2610.41023v1 Announce Type: cross Abstract: Omniprediction concerns the task of making predictions that are simultaneously accurate with respect to different losses. Earlier results by [CV09] show that in an…
arXiv:2610.42069v1 Announce Type: cross Abstract: Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear…
arXiv:2610.40667v1 Announce Type: cross Abstract: Median genomes serve as candidates for ancestral reconstruction and help study the diversity of parsimonious rearrangement solutions. However, the breakpoint median…
arXiv:2610.40625v2 Announce Type: replace-cross Abstract: In capacitated $(k,z)$-clustering, we open $k$ centers and assign every client to a center within its capacity, minimizing the sum of $z$-th powers of the…
arXiv:2610.41666v1 Announce Type: new Abstract: In the metric Steiner tree problem, we are given an $n$-point metric space $(V,w)$ and a set of terminals $T\subseteq V$, and we are interested in the smallest total…
arXiv:2610.40824v1 Announce Type: new Abstract: Distributional paging seeks a polynomial-time eviction rule that competes with the optimal \emph{online} policy $\mathrm{OPT}$ when requests come from a known stochastic…
arXiv:2509.07155v3 Announce Type: replace-cross Abstract: Important nonlinear dynamics, such as those found in plasma and fluid systems, are typically hard to simulate on classical computers. Thus, if fault-tolerant…
arXiv:2503.24373v2 Announce Type: replace Abstract: We provide $m^{1+o(1)}k\epsilon^{-1}$-time algorithms for computing multiplicative $(1 - \epsilon)$-approximate solutions to multi-commodity flow problems with…
arXiv:2610.40844v1 Announce Type: new Abstract: We introduce the Stochastic MST Identification Problem, with binary weights. In this problem, we need to identify a minimum spanning tree (MST) of a graph, each of whose…
arXiv:2610.41945v1 Announce Type: new Abstract: We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\left(\sqrt{\frac{\log n}{\log\log…
arXiv:2610.42067v1 Announce Type: cross Abstract: Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges…
arXiv:2610.41187v1 Announce Type: new Abstract: We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first…
arXiv:2610.42081v1 Announce Type: cross Abstract: Research on practical differentially private (DP) synthetic data has largely focused on methods that approximately preserve low-dimensional marginals of a target…
arXiv:2610.42075v1 Announce Type: cross Abstract: Let $P$ be a simple polygon with $m$ vertices. After $O(m)$-time preprocessing of $P$, for any set $S$ of $n$ additively weighted point sites, we compute an implicit…
arXiv:2610.41821v1 Announce Type: new Abstract: The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due…
arXiv:2610.40941v1 Announce Type: cross Abstract: We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. We…
Showing 1 day · 67 items available
