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.

25 Sep 2026 edition

60 articles · 3 sources · 60 papers ·

Top topics: Algorithms · AI

Algorithms

Claim-Gated Source-Risk Auditing for Generative Search

arXiv:2609.29145v1 Announce Type: cross Abstract: A generative search answer can cite a supported passage yet omit a source relationship that changes its interpretation. We specify a claim-gated audit of the…

Source: arXiv cs.CC Kainan Zhou, Chuhong Xu, Gangzhen Qian, Zhaoyi Li
Algorithms

A Polynomial-Time Test for Peak-Oriented Rationalizability

arXiv:2609.30042v1 Announce Type: cross Abstract: We study the computational complexity of peak-oriented rationalizability, a survey based revealed-preference test introduced by Seror (2026). We provide a…

Source: arXiv cs.CC Taotao He, Runfa Hu
Algorithms

A General Composition Theorem for Approximate Degree

arXiv:2609.30139v1 Announce Type: new Abstract: A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general…

Source: arXiv cs.CC Samruddhi Pednekar, Supartha Podder
Algorithms

Exact Quantum Circuit Optimization is co-NQP-hard

arXiv:2510.16420v3 Announce Type: replace-cross Abstract: As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical…

Source: arXiv cs.CC Adam Husted Kjelstr{\o}m, Andreas Pavlogiannis, Jaco van de Pol
Algorithms

Quantum Query Advantage Requires Space

arXiv:2609.29497v1 Announce Type: cross Abstract: Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a…

Source: arXiv cs.CC Minbo Gao, Zhengfeng Ji, Ziyi Xie
Algorithms

Exponential Correlation Bounds for Polynomials

arXiv:2609.28839v1 Announce Type: new Abstract: We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over…

Source: arXiv cs.CC Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola
Algorithms

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

arXiv:2609.29120v1 Announce Type: new Abstract: For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the…

Source: arXiv cs.CC Daqing Wan, Jun Zhang
Algorithms

On the SoS Certifiability of Log-Concave Distributions

arXiv:2609.30105v1 Announce Type: cross Abstract: For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a…

Source: arXiv cs.CC Aleksandr Storozhenko
Algorithms

Sharp Lovasz-Theta Bounds on Random Graphs

arXiv:2609.30064v1 Announce Type: cross Abstract: It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $\Theta(\sqrt{n})$. More precisely, it is tightly concentrated in the interval…

Source: arXiv cs.DM Aaron Potechin, Jeff Xu
Algorithms

The Richness of CSP Non-redundancy

arXiv:2507.07942v3 Announce Type: replace Abstract: In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of…

Source: arXiv cs.DM Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlstr\"om
Algorithms

On the Binary Rank of Matrices with Constant Real Rank

arXiv:2609.30203v1 Announce Type: cross Abstract: We continue the study initiated by Parnas and Shraibman~\cite{PARNAS2026264} who gave upper bounds on the binary rank of $0,1$ matrices which have a small rank over the…

Source: arXiv cs.DM Michal Parnas

Showing 1 day · 60 items available