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.13999v1 Announce Type: new Abstract: We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of…
arXiv:2608.13972v1 Announce Type: new Abstract: In this paper, we address a semi-infinite LP relaxation of the vector-subspace packing problem. This is a higher-dimensional generalization of the fractional linear…
arXiv:2605.25078v2 Announce Type: replace Abstract: Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" $G = (U \cup V, E)$, where the goal is to select exactly one…
arXiv:2608.13970v1 Announce Type: new Abstract: Near capacity, a cuckoo filter may reject an insertion even though a legal placement still exists: the table remains structurally feasible, but a bounded policy fails to…
arXiv:2409.02833v2 Announce Type: replace-cross Abstract: An $\ell$-page stack layout (also known as an $\ell$-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge…
arXiv:2606.21497v2 Announce Type: replace-cross Abstract: Modern deep neural networks are trained using error backpropagation, which requires sequential forward and backward computations across network layers. As these…
arXiv:2608.14201v1 Announce Type: new Abstract: For $d \geq 2$, $p \geq 1$ and $\epsilon > 0$, let $N_p(d,\epsilon)$ be the smallest integer $N$ such that for every integer $n$ and every $A\in\mathbb{R}^{n\times d}$,…
arXiv:2608.13910v1 Announce Type: new Abstract: A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted…
arXiv:2608.13983v1 Announce Type: new Abstract: We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every…
arXiv:1711.10051v4 Announce Type: replace-cross Abstract: We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial…
arXiv:2608.13782v1 Announce Type: cross Abstract: The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean…
arXiv:2608.14486v1 Announce Type: new Abstract: The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been…
arXiv:2404.02692v3 Announce Type: replace Abstract: The explosion of data available in life sciences is fueling an increasing demand for expressive models and computational methods. Graph transformation is a model for…
arXiv:2608.13964v1 Announce Type: cross Abstract: For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states…
arXiv:2607.23111v2 Announce Type: replace Abstract: A numerical semigroup is a subset of the nonnegative integers, closed under addition and with finite complement. The size of the complement is its genus. The problem…
arXiv:2608.11195v3 Announce Type: replace-cross Abstract: AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of…
arXiv:2608.14529v1 Announce Type: new Abstract: For every constant $2 <\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we give a deterministic polynomial-time reduction from…
arXiv:2608.14305v1 Announce Type: new Abstract: It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error…
arXiv:2510.02583v3 Announce Type: replace Abstract: The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it…
