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:2509.22233v2 Announce Type: replace-cross Abstract: The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the…
arXiv:2605.29944v2 Announce Type: replace-cross Abstract: Strongly simulating a quantum circuit, that is, computing an output amplitude, can be done by summing the circuit's Feynman paths: a weighted count over…
arXiv:2608.19489v1 Announce Type: cross Abstract: We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a…
arXiv:2608.20077v1 Announce Type: new Abstract: Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such…
arXiv:2608.19538v1 Announce Type: new Abstract: Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path…
arXiv:2608.20018v1 Announce Type: new Abstract: In the Shortest Common Superstring (SCS) problem, one is given a set of strings and asked to find a shortest string containing every input string as a substring. The…
arXiv:2608.19952v1 Announce Type: new Abstract: We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning…
arXiv:2608.20230v1 Announce Type: new Abstract: This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release…
arXiv:2608.20175v1 Announce Type: new Abstract: We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying…
arXiv:2608.20051v1 Announce Type: cross Abstract: We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty…
arXiv:2607.02838v2 Announce Type: replace Abstract: A string $w$ is closed if $|w|=1$, or if $w$ has a non-empty proper border occurring only as its prefix and suffix. A maximal closed substring (MCS) is a maximal…
arXiv:2608.19623v1 Announce Type: cross Abstract: We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $\alpha\ge 7.1$, we show that an…
arXiv:2202.08870v2 Announce Type: replace Abstract: The \emph{Product Structure Theorem} for planar graphs (Dujmovi\'c et al.\ \emph{JACM}, \textbf{67}(4):22) states that any planar graph is contained in the strong…
arXiv:2608.19569v1 Announce Type: cross Abstract: The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube.…
arXiv:2512.11785v2 Announce Type: replace-cross Abstract: We consider the distribution of the top eigenvector $\widehat{v}$ of a spiked matrix model of the form $H = \theta vv^* + W$, in the supercritical regime where…
arXiv:2608.19505v1 Announce Type: new Abstract: A linear extension of a finite partially ordered set is a total ordering that respects the partial order. We give a deterministic exact algorithm that counts the linear…
arXiv:2608.06796v2 Announce Type: replace Abstract: We study online multi-level aggregation on finite rooted trees with a per-batch maximum-delay objective. A service pays for a rooted subtree and for the maximum…
arXiv:2608.20287v1 Announce Type: cross Abstract: We introduce the honeycomb hierarchy, a representation-theoretic framework that gives new asymptotic upper bounds on $R_2(\delta)$. Its first level is the two-row…
arXiv:2608.19916v1 Announce Type: cross Abstract: Phylogenetic networks are graphs that represent the evolutionary history of species. Recently, the class of orchard phylogenetic networks, which can be reduced by…
arXiv:2608.19869v1 Announce Type: cross Abstract: Marton's inner bound, the best-known achievable region for a general discrete memoryless broadcast channel, was proposed by Katalin Marton in 1979, and whether it always…
arXiv:2607.26271v2 Announce Type: replace-cross Abstract: Martinsson and Steiner recently proved that the fractional chromatic number of any $d$-degenerate triangle-free graph $G$ satisfies $\chi_f(G) =…
arXiv:2608.20036v1 Announce Type: cross Abstract: For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $…
arXiv:2509.09633v3 Announce Type: replace-cross Abstract: A $k$-net($n$) is a combinatorial design equivalent to $k-2$ mutually orthogonal Latin squares of order $n$. A relation in a net is a linear dependency over…
arXiv:2608.15724v2 Announce Type: replace-cross Abstract: The frequency $K_i$s ($i\in[4,n]$) are studied for symmetric traveling salesman problem ($TSP$) to characterize the structure properties of the edges inside and…
arXiv:2608.19468v1 Announce Type: cross Abstract: We prove that every finite point set of size at least $10^{11055931}$ has four collinear points or six points that pairwise see each other. This resolves the first open…
arXiv:2511.21144v3 Announce Type: replace-cross Abstract: For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of…
arXiv:2608.19414v1 Announce Type: cross Abstract: First formulated by Amarilli, Monet, and Suciu (arXiv:2401.16210, 2024), the Non-Cancelling Intersections (NCI) conjecture is an open problem in combinatorics stating…
arXiv:2608.19314v1 Announce Type: cross Abstract: Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally…
arXiv:2402.00791v3 Announce Type: replace Abstract: We introduce Hausdorff (complexity) classes, which yield canonical normal forms for the intermediate levels of the iterated exponential hierarchies, including the…
arXiv:2608.19787v1 Announce Type: cross Abstract: We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity.…
arXiv:2608.19822v1 Announce Type: new Abstract: Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the…
arXiv:2602.05541v3 Announce Type: replace-cross Abstract: Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a…
arXiv:2601.08057v2 Announce Type: replace Abstract: The Hanano Puzzle is a one-player game with gravity, where the goal is to make colored blocks make contact with flowers of the corresponding color. The game Jelly no…
