TILens turns technical updates into a focused daily brief: official releases,
trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2611.25011v1 Announce Type: cross Abstract: The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a…
arXiv:2505.10006v4 Announce Type: replace Abstract: Aggregating multiple input rankings into a consensus ranking is essential in various fields such as social choice theory, hiring, college admissions, web search, and…
arXiv:2302.14834v4 Announce Type: replace Abstract: In this paper, we investigate the conditions under which a concurrent system is able to guarantee convergence deterministically even without synchronization. In…
arXiv:2611.25157v1 Announce Type: new Abstract: We study community detection in the sparse two-community stochastic block model when an adversary may corrupt a small constant fraction of the edges of the observed graph.…
arXiv:2603.02825v2 Announce Type: replace Abstract: We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality…
arXiv:2610.36691v2 Announce Type: replace Abstract: In Principal Component Analysis (PCA), we are given as input a matrix $A\in\mathbb{R}^{n\times d}$ and an integer $k\leq d$, and the goal is to find the top $k$…
arXiv:2504.10399v4 Announce Type: replace-cross Abstract: Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error…
arXiv:2609.15677v3 Announce Type: replace Abstract: \(k\)-submodularity generalizes submodularity by allowing each selected element to be assigned one of \(k\) labels. We study the maximization of a non-monotone…
arXiv:2601.04423v2 Announce Type: replace Abstract: A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,\dots,n\}$, each assigned a positive weight. A query specifies an admissible…
arXiv:2609.29589v2 Announce Type: replace Abstract: In online bin packing with delay, items of sizes in $(0,1]$ arrive over time and may wait before being packed into unit-capacity bins. A service selects a nonempty…
arXiv:2611.24786v2 Announce Type: replace Abstract: SotSort is a stable comparison sort whose single code path runs with anything from a fixed 16 KB buffer to a full n-element buffer. Its core is a stable quicksort that…
arXiv:2611.25305v1 Announce Type: cross Abstract: Given $n$ points in $\mathbb{Q}^d$ and an integer $k$, the continuous Euclidean $k$-means problem asks for $k$ centers in $\mathbb{R}^d$ that minimize the sum of squared…
arXiv:2611.06470v3 Announce Type: replace-cross Abstract: Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers…
arXiv:2611.25143v1 Announce Type: cross Abstract: Let $R(k,l;t)$ denote the least $n$ such that every colouring of the $t$-subsets of an $n$-set with two colours has $k$ points all of whose $t$-subsets have the first…
arXiv:2610.33131v2 Announce Type: replace-cross Abstract: We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is open and locally eventually onto. In this setting,…
arXiv:2610.32192v4 Announce Type: replace-cross Abstract: An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been…
arXiv:2611.13693v3 Announce Type: replace-cross Abstract: Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case…
arXiv:2607.03405v2 Announce Type: replace Abstract: We show that the existence of an oddomorphism from a graph $F$ to a graph $G$ does not imply that $G$ is a minor of $F$. This answers a question posed by Roberson…
arXiv:2407.05827v5 Announce Type: replace-cross Abstract: Reed in 1998 conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{\Delta(G)+1+\omega(G)}{2} \rceil$. As a partial result, he proved the…
arXiv:2611.24997v1 Announce Type: cross Abstract: We prove that no binary linear $[65,9,\geqslant29]$ code exists, equivalently, that no even binary linear $[66,9,\geqslant30]$ code exists. Together with known…