TILens turns technical updates into a focused daily brief: official releases,
trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2504.15143v4 Announce Type: replace Abstract: In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$…
arXiv:2609.38075v1 Announce Type: cross Abstract: For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's…
arXiv:2609.37261v1 Announce Type: cross Abstract: Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often…
arXiv:2609.36421v1 Announce Type: new Abstract: Reinforcement learning (RL) is a powerful framework for robotic control, yet its practical application is often hindered by high sample complexity. This is particularly…
arXiv:2607.03278v2 Announce Type: replace-cross Abstract: Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum…
arXiv:2609.36050v1 Announce Type: cross Abstract: We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix.…
arXiv:2609.37636v1 Announce Type: cross Abstract: We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance…
arXiv:2609.38073v1 Announce Type: cross Abstract: We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized,…
arXiv:2609.37417v1 Announce Type: new Abstract: Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite…
arXiv:2607.17469v2 Announce Type: replace Abstract: How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer guaranteed? We study…
arXiv:2609.35927v1 Announce Type: new Abstract: The problem to establish a lower bound for $\mbox{AC}^0[p]$-Frege refutations of a system of polynomial equations over ${\bf F}_p$ was in K. (2024) reduced to the…
arXiv:2609.36072v1 Announce Type: new Abstract: We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph…
arXiv:2609.37319v1 Announce Type: new Abstract: The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas}…
arXiv:2609.15591v4 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.36186v1 Announce Type: cross Abstract: For a graph $H$, $\langle H \rangle$ denotes the class of all subdivisions of $H$ and $tw(H)$ denotes the treewidth of $H$. In this paper, we prove the following. For…
arXiv:2609.37978v1 Announce Type: cross Abstract: A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular $K_3$-irregular graph exists, settling the last…
arXiv:2609.37796v1 Announce Type: cross Abstract: A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most…
arXiv:2609.33705v2 Announce Type: replace-cross Abstract: A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically…
arXiv:2609.13632v2 Announce Type: replace Abstract: Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as…
arXiv:2401.07549v4 Announce Type: replace Abstract: Subshifts are sets of colorings of $\mathbb{Z}^d$ defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of…