Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
57 articles · 3 sources · 57 papers ·
Top topics: Algorithms · AI
arXiv:2609.20763v1 Announce Type: new Abstract: In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most…
arXiv:2609.20651v1 Announce Type: cross Abstract: Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an…
arXiv:2609.20335v1 Announce Type: new Abstract: Transformers have emerged as the dominant architecture in sequence modeling, achieving remarkable success in natural language processing and reasoning tasks. While…
arXiv:2112.14242v2 Announce Type: replace-cross Abstract: Ensuring security and integrity of elections constitutes an important challenge with wide-ranging societal implications. Classically, security guarantees can be…
arXiv:2609.19780v1 Announce Type: new Abstract: We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a…
arXiv:2609.20075v1 Announce Type: new Abstract: An instance of {\sc Pinwheel Packing} is a list of positive integers $a_1,\ldots,a_k$. A feasible schedule assigns one task to every integer time so that every interval of…
arXiv:2609.15926v2 Announce Type: replace-cross Abstract: While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether…
arXiv:2609.20636v1 Announce Type: cross Abstract: We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system…
arXiv:2606.14167v4 Announce Type: replace-cross Abstract: We prove that satisfiability for existential Presburger arithmetic with divisibility (EPAD) is NEXP-hard. Together with the known NEXP upper bound, this…
arXiv:2609.20771v1 Announce Type: new Abstract: Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given…
arXiv:2609.19623v1 Announce Type: new Abstract: We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets,…
arXiv:2009.11318v2 Announce Type: replace-cross Abstract: For a simple undirected graph $G$, we derive exact formulae for the number of copies of each of the 21 non-isomorphic connected graphs on five vertices. For nine…
arXiv:2609.20281v1 Announce Type: cross Abstract: The contextual fraction measures how much globally consistent probability can be packed beneath prescribed local event probabilities. We study the quantitative regime in…
arXiv:2609.19214v1 Announce Type: cross Abstract: Socolar and Taylor asked for a single, simply connected three-dimensional prototile that forces nonperiodicity by shape alone, admitting no weakly nonperiodic tiling;…
arXiv:2609.19240v1 Announce Type: new Abstract: The Roman Domination Problem (RDP) on a graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) is adjacent…
arXiv:2609.19703v1 Announce Type: cross Abstract: In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A = \sum_{k=1}^m A_k…
arXiv:2609.12214v2 Announce Type: replace-cross Abstract: We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of…
arXiv:2609.20678v1 Announce Type: cross Abstract: We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include…
arXiv:2605.04734v3 Announce Type: replace-cross Abstract: Let $D_d(m)$ be the Cartesian product of $d$ positively oriented directed cycles of length $m$. We prove that $D_d(m)$ decomposes into $d$ directed Hamilton…
arXiv:2609.20366v1 Announce Type: cross Abstract: We consider infinite walks in $\mathbb{N}^k$ with standard unit basis vector steps that avoid $t$ collinear points, and show that these walks exist for $(k,t) \in…
Showing 1 day · 57 items available
