Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
13 articles · 2 sources · 13 papers ·
Top topics: Algorithms · AI
arXiv:2211.02107v2 Announce Type: replace Abstract: In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends…
arXiv:2202.10527v3 Announce Type: replace Abstract: A proper circular-arc (PCA) model is a pair $M = (C, A)$ where $C$ is a circle and $A$ is a family of inclusion-free arcs on $C$ whose extremes are pairwise different.…
arXiv:2506.02982v3 Announce Type: replace-cross Abstract: In 2010 Banderier and Nicodeme consider the height of bounded discrete bridges and conclude to a limiting Rayleigh distribution. This result is correct although…
arXiv:2312.03399v3 Announce Type: replace-cross Abstract: A dominating set of a graph $G$ is \emph{connected} if it induces a connected graph in $G$. For planar triangulations, it has been known since 1990 that every…
arXiv:2609.17266v2 Announce Type: replace-cross Abstract: We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with…
arXiv:2609.11285v2 Announce Type: replace-cross Abstract: We show that Max Independent Set (MIS) remains NP-hard in graphs excluding the $5 \times 5$ grid as an induced minor. This negatively answers a question of…
arXiv:2607.10667v2 Announce Type: replace-cross Abstract: For a relational structure A, the Minimum Cost Constraint Satisfaction Problem is the following problem denoted by MinCostCSP(A): Given an instance of CSP(A)…
arXiv:2610.03550v2 Announce Type: replace-cross Abstract: We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph class closed under minors and disjoint unions strictly increases…
arXiv:2608.01320v2 Announce Type: replace-cross Abstract: Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive…
arXiv:2305.07271v2 Announce Type: replace-cross Abstract: A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose arcs are labeled with…
arXiv:2607.14238v2 Announce Type: replace-cross Abstract: The celebrated (offline) Beck--Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has…
arXiv:2608.25491v2 Announce Type: replace-cross Abstract: It is proved that, for every $\delta \in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq…
arXiv:2609.35711v3 Announce Type: replace-cross Abstract: We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily…
