Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
60 articles · 3 sources · 60 papers ·
Top topics: Algorithms · AI
arXiv:2604.07460v2 Announce Type: replace-cross Abstract: In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $\rho$, test whether it matches some…
arXiv:2609.30171v1 Announce Type: cross Abstract: We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[…
arXiv:2609.28708v1 Announce Type: new Abstract: We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a…
arXiv:2609.30193v1 Announce Type: new Abstract: The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence. It is this phrase count,…
arXiv:2609.30052v1 Announce Type: new Abstract: In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time…
arXiv:2609.30089v1 Announce Type: new Abstract: Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics. Bi-directional r-indexes support left- and right-extension of a pattern…
arXiv:2609.29589v1 Announce Type: new Abstract: We study online bin packing with per-bin maximum delay: each sealed bin incurs a unit opening cost plus the longest waiting time among its items. Offline, this becomes a…
arXiv:2608.28094v3 Announce Type: replace Abstract: We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot…
arXiv:2609.30215v1 Announce Type: new 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 linear…
arXiv:2609.27921v2 Announce Type: replace Abstract: In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a…
arXiv:2510.02727v2 Announce Type: replace Abstract: Recombining trinomial trees are a workhorse for modeling discrete-event systems in option pricing, logistics, and feedback control. Because each node stores a…
arXiv:2607.08556v2 Announce Type: replace Abstract: We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries…
arXiv:2511.09703v4 Announce Type: replace-cross Abstract: A zero-one matrix is a matrix with entries from $\{0, 1\}$. We study monoids containing only such matrices. A finite set of zero-one matrices generating such a…
arXiv:2609.29451v1 Announce Type: new Abstract: We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a…
arXiv:2609.29324v1 Announce Type: new Abstract: We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs…
arXiv:2609.24931v2 Announce Type: replace Abstract: Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and…
arXiv:2511.08958v3 Announce Type: replace Abstract: The longest common bitonic subsequence problem asks for a longest common subsequence of two ordered sequences whose values strictly increase and then strictly…
arXiv:2609.19794v2 Announce Type: replace Abstract: Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer…
arXiv:2609.28528v1 Announce Type: cross Abstract: The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and…
arXiv:2609.29881v1 Announce Type: cross Abstract: Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or…
Showing 1 day · 60 items available
