TILens turns technical updates into a focused daily brief: official releases,
trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2609.30757v1 Announce Type: new Abstract: In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev…
arXiv:2609.31223v1 Announce Type: cross Abstract: We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known…
arXiv:2609.31053v1 Announce Type: new Abstract: Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership…
arXiv:2609.31520v1 Announce Type: cross Abstract: For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization…
arXiv:2609.31517v1 Announce Type: new Abstract: We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its…
arXiv:2605.04330v3 Announce Type: replace-cross Abstract: We investigate the scaling properties of implicit deductive reasoning over Horn clauses in depth-bounded Transformers. By discouraging the reliance on…
arXiv:2609.30888v1 Announce Type: cross Abstract: The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an…
arXiv:2609.15591v3 Announce Type: replace-cross Abstract: We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside…
arXiv:2609.30302v1 Announce Type: new Abstract: In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths.…
arXiv:2504.02593v2 Announce Type: replace-cross Abstract: We study the maximum level-$1$ Fourier weight of Boolean functions, which is equivalent to the minimum average-distance problem on the hypercube. We first…
arXiv:2608.27179v2 Announce Type: replace-cross Abstract: In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an…
arXiv:2507.17654v4 Announce Type: replace-cross Abstract: Function-correcting codes are a coding framework designed to minimize redundancy while ensuring that specific functions or computations of encoded data can be…
arXiv:2609.31205v1 Announce Type: new Abstract: For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting…
arXiv:2609.30895v1 Announce Type: cross Abstract: Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing…
arXiv:2603.17730v4 Announce Type: replace-cross Abstract: In recent work, Martinsson and Steiner proved that triangle-free $d$-degenerate graphs have fractional chromatic number $\chi_f(G) = O\left(\frac{d}{\log…
arXiv:2609.30742v1 Announce Type: cross Abstract: We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose…
arXiv:2609.30992v1 Announce Type: new Abstract: We give a deterministic algorithm for exact modular subset sum that, for every modulus m, computes all reachable residues and one requested witness in O(m) time and O(m)…
arXiv:2609.30778v1 Announce Type: new Abstract: Let $\lambda$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an…
arXiv:2609.30853v1 Announce Type: cross Abstract: Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can…
arXiv:2604.27745v2 Announce Type: replace Abstract: We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under…