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.19081v1 Announce Type: new Abstract: We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and…
arXiv:2608.18577v1 Announce Type: new Abstract: We study online service with one maximum-waiting-time charge per service batch. Requests arrive at points of a finite metric, and a mobile server pays for its movement…
arXiv:2605.16618v2 Announce Type: replace Abstract: We work in the adaptive query model, where one is given a point set $P \subset \mathbb{R}^d$ and seeks to construct a data structure that can answer correctly and…
arXiv:2603.02689v2 Announce Type: replace Abstract: As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors…
arXiv:2608.18402v1 Announce Type: cross Abstract: We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models.…
arXiv:2608.18147v1 Announce Type: cross Abstract: Adaptive stochastic quantization (ASQ) is a recently introduced quantization approach that optimizes the Mean Squared Error (MSE) for a given input while preserving…
arXiv:2508.15436v2 Announce Type: replace-cross Abstract: We propose a $\textbf{P}$latform for $\textbf{L}$ayout-$\textbf{A}$ware $\textbf{S}$earch and $\textbf{M}$emory $\textbf{A}$rrangement ($\textbf{PLASMA}$), a…
arXiv:2404.16349v3 Announce Type: replace Abstract: We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu,…
arXiv:2608.18992v1 Announce Type: cross Abstract: There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the {energy (a.k.a awake) complexity, which measures…
arXiv:2608.19050v1 Announce Type: cross Abstract: We study optimal online algorithms for embedding a permutation $\pi$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad…
arXiv:2511.22914v3 Announce Type: replace Abstract: This paper investigates the reconfiguration variant of the Constraint Satisfaction Problem (CSP), referred to as the Reconfiguration CSP (RCSP). Given a CSP instance…
arXiv:2503.13274v3 Announce Type: replace Abstract: For $n$-vertex $m$-edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem…
arXiv:2508.06478v3 Announce Type: replace Abstract: In this paper, we investigate the computational complexity of isomorphism testing for finite groups and quasigroups, given by their multiplication tables. We crucially…
arXiv:2604.00607v3 Announce Type: replace-cross Abstract: The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given $n$ car models that occur twice in a sequence of length $2n$, the…
arXiv:2608.18875v1 Announce Type: cross Abstract: For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points…
arXiv:2608.19092v1 Announce Type: new Abstract: For any tripartite relation $R\subseteq \mathbb{Z}^3$, the $R$-Triangle problem asks, given an edge-weighted graph, whether it contains a triangle whose weights form a…
arXiv:2608.18496v1 Announce Type: new Abstract: We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously…
arXiv:2608.19149v1 Announce Type: new Abstract: Suppose two parties, Alice and Bob, hold long character strings, $X$ and $Y$, respectively, and they are interested in determining how similar $X$ and $Y$ are. {Moreover,…
arXiv:2608.19172v1 Announce Type: new Abstract: For a text $T$ of length $n$ over an alphabet of size $\sigma$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its…
arXiv:2405.09141v4 Announce Type: replace Abstract: A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In…
arXiv:2608.18612v1 Announce Type: new Abstract: We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our…
arXiv:2608.19123v1 Announce Type: new Abstract: For a text $T\in[0..\sigma)^n$ with $2\leq\sigma\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each…
arXiv:2608.18772v1 Announce Type: new Abstract: Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election…
arXiv:2607.16347v5 Announce Type: replace Abstract: Scheduling $n$ jobs with deadlines and processing times on a single resource to minimize late jobs equates to finding a maximum-cardinality feasible subset. Moore…
arXiv:2608.18837v1 Announce Type: new Abstract: We study makespan minimisation on two identical parallel machines that share a single server for both loading and unloading. Each job must be loaded, processed without…
arXiv:2608.17907v2 Announce Type: replace Abstract: We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $\sigma$ to answer…
arXiv:2607.14745v3 Announce Type: replace Abstract: Enumerating simple paths and cycles subject to a given length bound is a fundamental problem in graph algorithms. Recent algorithms, namely BC-DFS (Peng et al. 2019,…
arXiv:2608.18514v1 Announce Type: cross Abstract: The two-dimensional bandwidth minimization problem (2DBMP) seeks an injective embedding of a guest graph into a square grid that minimizes the maximum Manhattan distance…
arXiv:2603.17819v2 Announce Type: replace-cross Abstract: Alternate bases are a numeration system that generalizes the R\'enyi numeration system. It is common in this context to construct examples or counter-examples by…
arXiv:2602.18427v2 Announce Type: replace-cross Abstract: We study the convex hulls of $n \times n$ alternating sign matrices invariant under subgroups of the dihedral group of the square. For each non-trivial symmetry…
arXiv:2608.18910v1 Announce Type: cross Abstract: Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as…
arXiv:2501.00157v2 Announce Type: replace-cross Abstract: Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding to the vertices. Next, let the polynomial $p_H$ be…
arXiv:2608.18617v1 Announce Type: cross Abstract: In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$…
arXiv:2608.18769v1 Announce Type: cross Abstract: The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$…
arXiv:2510.06533v3 Announce Type: replace Abstract: In the covering version of the pinwheel scheduling problem, a daily task must be assigned to agents under the constraint that agent $i$ can perform the task at most…
arXiv:2608.18194v1 Announce Type: cross Abstract: This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly…
arXiv:2608.18445v1 Announce Type: cross Abstract: We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning…
arXiv:2608.18854v1 Announce Type: new Abstract: For graphs of rank-width \(w\), the algorithms of Bui-Xuan, Telle, and Vatshelle (\emph{Theor. Comput. Sci.}, 2013) for fixed finite/cofinite \((\sigma,\rho)\)-problems…
arXiv:2608.14529v3 Announce Type: replace Abstract: For every constant $2 <\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the $\ell_p$-shortest vector problem for…
arXiv:2405.08051v3 Announce Type: replace Abstract: This paper investigates an extremely classic NP-complete problem: How to determine if a graph G, where each vertex has a degree of at most 4, can be 3-colorable(The…
arXiv:2608.18839v1 Announce Type: cross Abstract: We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or…
arXiv:2608.18784v1 Announce Type: new Abstract: We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial…
arXiv:2608.17109v2 Announce Type: replace-cross Abstract: Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight…
arXiv:2608.18917v1 Announce Type: cross Abstract: We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the…
arXiv:2608.18536v1 Announce Type: cross Abstract: Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for…
arXiv:2608.19158v1 Announce Type: cross Abstract: One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a…
