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.

01 Oct 2026 edition

90 articles · 3 sources · 90 papers ·

Top topics: Algorithms · AI

Algorithms AI

Security Properties of Neural Networks as Decision Problems

arXiv:2609.39768v1 Announce Type: cross Abstract: Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its…

Source: arXiv cs.CC Adrian Wurm
Algorithms

Improved Quantum Random Self-Reduction for Linear Problems

arXiv:2609.39823v1 Announce Type: cross Abstract: We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an…

Source: arXiv cs.CC Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
Algorithms

Karp's NP-complete problems over first-order definable structures

arXiv:2609.38436v1 Announce Type: cross Abstract: We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets…

Source: arXiv cs.CC Aidan Healy, Bartek Klin
Algorithms

QMA(2) with Limited Shared Entanglement

arXiv:2609.39668v1 Announce Type: cross Abstract: A $\mathsf{QMA}(2)$ protocol involves two provers submitting unentangled witnesses to a polynomial-time quantum verifier. In The Power of Unentanglement (ToC, 2009),…

Source: arXiv cs.CC Alex Della Schiava, Ranitha Mataraarachchi
Algorithms

SC Derandomization for Regular ROBPs and Models Beyond BPL

arXiv:2609.23603v2 Announce Type: replace Abstract: We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and…

Source: arXiv cs.CC Kuan Cheng, Ruiyang Wu
Algorithms

On quantum interactive proofs with a laconic prover

arXiv:2609.39495v1 Announce Type: cross Abstract: Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover…

Source: arXiv cs.CC Zihan Hu, Yupan Liu
Algorithms

A Separation Between Types of Quantum Oracle Separations

arXiv:2609.38704v1 Announce Type: cross Abstract: Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query…

Source: arXiv cs.CC Scott Aaronson, Adam Bouland, Jordan Docter, Barak Nehoran
Algorithms

Discrepancy for Random Linear Codes

arXiv:2606.24471v2 Announce Type: replace-cross Abstract: We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general…

Source: arXiv cs.CC Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, Jo\~ao Ribeiro
Algorithms

Planted Cliques and Quantum Symmetry-Adapted Measurements

arXiv:2609.40310v1 Announce Type: cross Abstract: The planted clique problem is a promising candidate for quantum advantage with a wide computational-statistical gap and substantial evidence for classical hardness. We…

Source: arXiv cs.CC Vojtech Havlicek, Jordan Docter, Subhash Khot
Algorithms

A physical and universal model of bosonic computations with Solovay-Kitaev theorem

arXiv:2609.40226v1 Announce Type: cross Abstract: Bosonic quantum systems are among the leading architectures for quantum information processing, offering continuous-variable degrees of freedom with strong…

Source: arXiv cs.CC Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani, Hamid Reza Naeij, Ulysse Chabaud, Sevag Gharibian, Saeed Mehraban
Algorithms

Exponential Quantum Advantage in Numbers-on-Forehead Communication

arXiv:2609.40273v1 Announce Type: new Abstract: We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold…

Source: arXiv cs.CC Haoyu Wang, Pei Wu, Guangxu Yang
Algorithms

Quantum Lazy Sampling and Path Recording for Any Group

arXiv:2606.30281v2 Announce Type: replace-cross Abstract: A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function,…

Source: arXiv cs.CC Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, John Wright

Showing 1 day · 90 items available