Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
58 articles · 3 sources · 58 papers ·
Top topics: Algorithms · AI · Information Retrieval
arXiv:2610.11145v1 Announce Type: new Abstract: We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown…
arXiv:2610.09618v2 Announce Type: replace Abstract: For every fixed proper minor-closed class $\mathscr C$ and every $\epsilon>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most…
arXiv:2608.08616v3 Announce Type: replace Abstract: We establish counting and sampling analogues of the Lov\'asz Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying…
arXiv:2610.12239v1 Announce Type: cross Abstract: We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order $s$ of a $C^{s,1}$ function…
arXiv:2610.12312v1 Announce Type: new Abstract: Large-scale information retrieval systems, including retrieval-augmented generation (RAG) and recommendation engines, widely use multi-layered hierarchical data structures…
arXiv:2610.12195v1 Announce Type: new Abstract: We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances…
arXiv:2604.12653v2 Announce Type: replace Abstract: In 1972, Fredman proposes the problem of sorting under partial information: preprocess a directed acyclic graph $G$ with vertex set $X$ so that you can sort $X$ in…
arXiv:0901.4417v5 Announce Type: replace Abstract: By definition an anticlique is an independent set of vertices of a graph $G$. By duality all results obtained for anticliques carry over to cliques. (It is for…
arXiv:2610.10904v1 Announce Type: new Abstract: We prove an $\Omega((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability…
arXiv:2610.10898v1 Announce Type: new Abstract: We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size…
arXiv:2610.11944v1 Announce Type: new Abstract: In this paper, we refine the dynamic programming framework based on the sphere cut decomposition designed by Dorn, Penninkx, Bodlaender, and Fomin (ESA 2005) to obtain…
arXiv:2610.12438v1 Announce Type: new Abstract: In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such…
arXiv:2610.11426v1 Announce Type: cross Abstract: Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the $n$-dimensional associahedron has chromatic number at most $22500\cdot\log_3 n+O(1)$. We present a much…
arXiv:2610.10282v2 Announce Type: replace Abstract: We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with…
arXiv:2610.11481v1 Announce Type: new Abstract: We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli…
arXiv:2607.22063v2 Announce Type: replace Abstract: HyperLogLog is a now classic probabilistic algorithm that provides an approximation of the number of distinct elements in a massive dataset, using only one pass over…
arXiv:2610.12456v1 Announce Type: new Abstract: For $\Delta\ge2$ and $q\ge11\Delta/6$, we prove that the antiferromagnetic $q$-state Potts partition function on finite simple graphs of maximum degree at most $\Delta$…
arXiv:2603.14293v2 Announce Type: replace Abstract: In the online hitting set problem, sets arrive over time, and the algorithm has to maintain a subset of elements that hit all the sets seen so far. Alon, Awerbuch,…
arXiv:2610.10596v1 Announce Type: new Abstract: Dijkstra's algorithm is almost universally classified as a canonical greedy algorithm. This paper challenges that conventional interpretation and presents a simple, direct…
arXiv:2608.03351v3 Announce Type: replace Abstract: The Lempel-Ziv (LZ) factorization is a fundamental method for compressing repetitive strings. Its multiplicative sensitivity to an operation measures how much that…
Showing 1 day · 58 items available
