Skip to content
TILens What matters today in tech v0.3.2
Theme

Daily edition · Algorithms

The daily ledger

TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.

30 Sep 2026 edition

56 articles · 3 sources · 56 papers ·

Top topics: Algorithms · AI

Algorithms

Deterministic Depth-4 PIT and Normalization

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$…

Source: arXiv cs.CC Zeyu Guo, Siki Wang
Algorithms

Ramanujan quantum expanders from the Weil representation

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…

Source: arXiv cs.CC Siddhartha Jain
Algorithms AI

Efficiently Approximating Attention Is Hard

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…

Source: arXiv cs.CC Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe, Marco Pavone
Algorithms

Sample Complexity of Equivariant Reinforcement Learning

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…

Source: arXiv cs.CC Rayan Mazouz, Haibo Zhao, Chris Hillar, Christian Shewmake
Algorithms

From Weak to Strong Testing in Gaussian Models

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.…

Source: arXiv cs.CC Ansh Nagda, Alexander S. Wein
Algorithms

Resonance Breaking in Noisy Shor's Algorithm

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…

Source: arXiv cs.CC Zhengwei Liu
Algorithms

Optimal Quantum-Classical Separations for Exact Learning

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,…

Source: arXiv cs.CC Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
Algorithms

Robust Approximation and the Arity Barrier at Width Two

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…

Source: arXiv cs.CC Nathan Benedetto Proen\c{c}a, Kopp\'any Istv\'an Encz, Monaldo Mastrolilli
Algorithms

Local Search with Correlated Randomness

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…

Source: arXiv cs.CC Yunbei Xu
Algorithms

Spectral Methods for the Complexity of Planar Graph Homomorphisms

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…

Source: arXiv cs.CC Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
Algorithms

There is no $8$-regular $K_3$-irregular graph

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…

Source: arXiv cs.DM Artem Hak, Sergiy Kozerenko, Andrii Serdiuk
Algorithms

Structural and computational aspects of majority coloring games

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…

Source: arXiv cs.DM Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan, Eshwar Srinivasan
Algorithms

Flip-packability: uniform characterisations of tame graph classes

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…

Source: arXiv cs.DM Ioannis Eleftheriadis
Algorithms

Oblivious Self-Distance Symmetric Rendezvous on the Integer Line

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…

Source: arXiv cs.DM Konstantinos Georgiou, Claude Gravel, Joey Kapusin, Lazar Mandic

Showing 1 day · 56 items available