Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
57 articles · 3 sources · 57 papers ·
Top topics: Algorithms · AI
arXiv:2509.13448v2 Announce Type: replace-cross Abstract: Efficient routing is critical for payment channel networks (PCNs) such as the Lightning Network (LN), where shortest-path computations are commonly performed…
arXiv:2609.19940v1 Announce Type: cross Abstract: In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity…
arXiv:2609.20238v1 Announce Type: new Abstract: We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric,…
arXiv:2609.19794v1 Announce Type: new Abstract: Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem.…
arXiv:2609.20337v1 Announce Type: new Abstract: In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most…
arXiv:2609.19685v1 Announce Type: cross Abstract: We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This…
arXiv:2410.23969v3 Announce Type: replace-cross Abstract: We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place…
arXiv:2609.19943v1 Announce Type: new Abstract: Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs,…
arXiv:2609.20061v1 Announce Type: new Abstract: The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is…
arXiv:2609.19397v1 Announce Type: cross Abstract: Figured-bass realization can be described as a sequence of choices constrained both within each sonority and between successive sonorities. This paper gives an explicit…
arXiv:2609.20717v1 Announce Type: new Abstract: We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde{O}(n^{3.5}\varepsilon^{-2})$. Our algorithm extends to a strongly…
arXiv:2609.20699v1 Announce Type: new Abstract: We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The…
arXiv:2609.19960v1 Announce Type: new Abstract: Computing influence spread under the Independent Cascade (IC) model is #P-hard, and influence maximization is commonly approached using Monte Carlo or…
arXiv:2609.20241v1 Announce Type: new Abstract: We propose Volume Appproximate Cholesky (VAC), an alternative sampling rule for practical approximate Cholesky algorithms. Our rule samples a uniformly random spanning…
arXiv:2609.20796v1 Announce Type: new Abstract: For every $0 < \varepsilon \le 1$, we give a randomized $(3+\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented…
arXiv:2609.19746v1 Announce Type: new Abstract: A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of…
arXiv:2609.18023v2 Announce Type: replace-cross Abstract: Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with…
arXiv:2609.19157v1 Announce Type: new Abstract: We study the competitive ratio of Longest Queue Drop (LQD), the canonical buffer management policy for shared memory switches, for which the previously published bounds…
arXiv:2410.14638v4 Announce Type: replace Abstract: Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex $s$ to a given vertex $t$, in practice…
arXiv:2609.19714v1 Announce Type: new Abstract: We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix…
Showing 1 day · 57 items available
