Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
90 articles · 3 sources · 90 papers ·
Top topics: Algorithms · AI
arXiv:2609.23458v2 Announce Type: replace Abstract: For a fixed integer $r\geq4$, the $K_r-e$-free graph sandwich problem asks whether, given graphs $G_1\subseteq G_2$ on the same vertex set, there is an…
arXiv:2609.39349v1 Announce Type: new Abstract: We study multidimensional resource scheduling. Each job $i$ has a $d$-dimensional resource-demand vector $v_i$ and a processing time $s_i$. The scheduler assigns a start…
arXiv:2609.40277v1 Announce Type: cross Abstract: We present an efficient quantum algorithm for the non-uniform Chebyshev transform. It is defined as the projection of a function onto Chebyshev polynomials sampled at…
arXiv:2609.40293v1 Announce Type: cross Abstract: In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial…
arXiv:2608.24493v2 Announce Type: replace-cross Abstract: Suppose we can apply the unitary $U=e^{i H}$ for some Hamiltonian $H$, and are given access to a unitary that prepares a guiding state promised to have overlap…
arXiv:2508.19473v3 Announce Type: replace Abstract: This paper shows a polynomial-time algorithm that, given a general matroid $M_1$ and $k-1$ partition matroids $ M_2, \ldots, M_k$, produces a coloring of the…
arXiv:2609.40302v1 Announce Type: cross Abstract: We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm…
arXiv:2609.39617v1 Announce Type: new Abstract: For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly…
arXiv:2609.39457v1 Announce Type: new Abstract: Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect…
arXiv:2609.38686v1 Announce Type: new Abstract: We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph (#SubgraphIsomorphism), motivated by network motif search.…
arXiv:2609.40147v1 Announce Type: cross Abstract: We establish an exponential iteration lower bound in the number of states for Howard's policy iteration on deterministic discounted Markov decision processes, with at…
arXiv:2609.40217v1 Announce Type: cross Abstract: The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many…
arXiv:2609.40167v1 Announce Type: cross Abstract: We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|{\psi}\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of…
arXiv:2302.02006v2 Announce Type: replace-cross Abstract: Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent…
arXiv:2609.38726v1 Announce Type: cross Abstract: In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two…
arXiv:2609.40249v1 Announce Type: new Abstract: Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings $S,T$ over an alphabet…
arXiv:2609.39052v1 Announce Type: new Abstract: We study the \emph{online transportation problem}, in which $n$ requests arriving sequentially in a metric space must be irrevocably assigned to $k$ capacitated…
arXiv:2609.39233v1 Announce Type: cross Abstract: We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the…
arXiv:2508.02249v4 Announce Type: replace-cross Abstract: For an integer full column rank matrix $A$, we consider the lattice that consists of all integer combinations of columns of $A$. We prove that a shortest…
arXiv:2609.40345v1 Announce Type: cross Abstract: We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to…
Showing 1 day · 90 items available
