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.10523v1 Announce Type: new Abstract: \texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in…
arXiv:2608.10674v1 Announce Type: cross Abstract: The Uhlmann fidelity ${\rm F}(\rho_0,\rho_1) = {\rm tr}|\sqrt{\rho_0}\sqrt{\rho_1}|$ is one of the most fundamental quantities in quantum information theory for…
arXiv:2608.10147v1 Announce Type: new Abstract: We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms,…
arXiv:2608.10416v1 Announce Type: new Abstract: We present a theoretical foundation for inverse-distance attention, from its Euclidean prototype (Resolver) to its non-Euclidean realization (Riemann GeoResolver). The…
arXiv:2608.11163v1 Announce Type: new Abstract: We show that a simple extension of the randomized greedy maximal independent set algorithm yields a constant approximation for the maximum matching problem. The algorithm…
arXiv:2608.11038v1 Announce Type: new Abstract: We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given two vertices $s,t$, find a shortest walk from $s$ to $t$ that visits every vertex. Our…
arXiv:2504.21601v3 Announce Type: replace-cross Abstract: Discrete Forman-Ricci curvature (FRC) is an efficient tool that characterizes essential geometrical features and associated transitions of real-world networks,…
arXiv:2505.21460v2 Announce Type: replace-cross Abstract: We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P \subset \mathbb{R}^d$ relative to an arbitrary norm $|\cdot|$. We…
arXiv:2608.10326v1 Announce Type: cross Abstract: We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for…
arXiv:2607.13284v2 Announce Type: replace Abstract: The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a…
arXiv:2608.10184v1 Announce Type: cross Abstract: Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for…
arXiv:2608.10193v1 Announce Type: cross Abstract: We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs, possibly with loops, indexed by the edges of a forest $G$. We also…
arXiv:2608.11158v1 Announce Type: cross Abstract: We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6\pi}{11} \le K_G \le \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound…
arXiv:2608.10040v1 Announce Type: new Abstract: We study online discrepancy minimization: vectors $v_1,\ldots,v_T\in\mathbb{R}^n$ arrive sequentially, and each must immediately be assigned a sign $x_t\in\{\pm1\}$, with…
arXiv:2604.12036v3 Announce Type: replace Abstract: We study a well-known task of constructing a decision tree identifying an unknown hypothesis from a given ground set of hypotheses under both the average- and…
arXiv:2608.10848v1 Announce Type: new Abstract: We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as…
arXiv:2608.10135v1 Announce Type: new Abstract: A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold.…
arXiv:2608.10376v1 Announce Type: new Abstract: A set of intervals $I = \{ I_1, I_2, \dots, I_n \}$ forms a simple chain if, for every $2\leq i \leq n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We…
arXiv:2608.11057v1 Announce Type: new Abstract: We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of…
arXiv:2603.12894v3 Announce Type: replace Abstract: The BEST theorem, due to de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, is a classical tool from graph theory that links the Eulerian trails in a directed graph…
arXiv:2608.10753v1 Announce Type: new Abstract: Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot…
arXiv:2608.10421v1 Announce Type: new Abstract: In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $nH+3n$ comparisons and…
arXiv:2506.16021v2 Announce Type: replace-cross Abstract: The problem of locally routing on geometric networks using limited memory is extensively studied in computational geometry. We consider one particular graph, the…
arXiv:2309.09359v3 Announce Type: replace-cross Abstract: Skiplists are used in a variety of applications for storing data subject to order criteria. In this article we discuss the design, analysis and performance of a…
arXiv:2608.11094v1 Announce Type: new Abstract: In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where…
arXiv:2608.10380v1 Announce Type: new Abstract: A connectivity function on a finite set $E$ is a function $f\colon 2^E\to\mathbb Z$ that is submodular and symmetric, with $f(\varnothing)=0$. Given a connectivity…
arXiv:2608.10617v1 Announce Type: new Abstract: For a connected graph $G = (V, E)$, a set $D \subseteq V$ is a co-secure dominating set if $D$ is a dominating set of $G$ and for each vertex $u \in D$ there exists a…
arXiv:2507.18776v2 Announce Type: replace-cross Abstract: We address the problem proposed by Chartrand, Erd\H{o}s and Oellermann (1988) about the existence of regular $K_3$-irregular graphs. We first establish bounds on…
arXiv:2009.09674v2 Announce Type: replace-cross Abstract: Let $\mathcal G$ be a hypergraph whose edges are colored. An {\it $(\alpha,n)$-detachment} of $\mathcal G$ is a hypergraph obtained by splitting a vertex…
arXiv:2311.13523v3 Announce Type: replace-cross Abstract: We study the problem of gradually representing a complex graph as a sequence of drawings of small subgraphs whose union is the complex graph. The sequence of…
arXiv:2510.13705v3 Announce Type: replace-cross Abstract: We prove a support--shattering uncertainty principle for functions on the Boolean cube. Let $\mathbb{F}$ be any field and let $f:\{0,1\}^n\to\mathbb{F}$ be…
arXiv:2608.10874v1 Announce Type: new Abstract: A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every…
arXiv:2608.11181v1 Announce Type: new Abstract: When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is…
arXiv:2608.11066v1 Announce Type: cross Abstract: We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary…
arXiv:2608.10179v1 Announce Type: new Abstract: A tensor has border rank at most $r$ if it can be written as $T=\lim_{\varepsilon \rightarrow 0} T(\varepsilon)$ where $T(\varepsilon)$ has rank at most $r$ for all…
arXiv:2608.11195v1 Announce Type: 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 how AI…
arXiv:2604.22627v2 Announce Type: replace-cross Abstract: Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(\rho^t)$, but whether replica number…
arXiv:2603.14846v4 Announce Type: replace-cross Abstract: We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing…
arXiv:2608.10696v1 Announce Type: new Abstract: Shellsort's best general lower and classical upper bounds differ by an iterated-logarithmic factor. Lower bounds use signed, order-free cancellation, whereas upper bounds…
