Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
65 articles · 3 sources · 65 papers ·
Top topics: Algorithms · AI
arXiv:2609.14110v2 Announce Type: replace-cross Abstract: Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the…
arXiv:2509.07835v2 Announce Type: replace-cross Abstract: Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the…
arXiv:2609.25680v1 Announce Type: cross Abstract: We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with…
arXiv:2609.25419v1 Announce Type: new Abstract: The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a…
arXiv:2609.25929v1 Announce Type: cross Abstract: We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state,…
arXiv:2609.26222v1 Announce Type: cross Abstract: We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random…
arXiv:2607.14316v3 Announce Type: replace-cross Abstract: We prove that every idempotent Schur multiplier is a finite signed sum of contractive idempotent Schur multipliers. This was conjectured by Katavolos and Paulsen…
arXiv:2609.26678v1 Announce Type: new Abstract: Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation…
arXiv:2609.26307v1 Announce Type: cross Abstract: The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$. The…
arXiv:2609.25483v1 Announce Type: new Abstract: We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These…
arXiv:2609.26047v1 Announce Type: cross Abstract: We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of…
arXiv:2606.31803v2 Announce Type: replace Abstract: Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems $\text{IndSub}(\Phi)$ for fixed graph properties $\Phi$: Given an input graph $G$ and $k\in\mathbb…
arXiv:2609.26735v1 Announce Type: cross Abstract: We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and…
arXiv:2608.18839v2 Announce Type: replace-cross Abstract: We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or…
arXiv:2604.01408v2 Announce Type: replace-cross Abstract: Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the…
arXiv:2609.25802v1 Announce Type: cross Abstract: We introduce latest exact match attention (LEMA), an attention variant for transformers where queries and keys are binarized and each query attends only to the latest…
arXiv:2609.26126v1 Announce Type: cross Abstract: Many AI systems make decisions locally, even when every realized output must obey an additive conservation law, such as selecting exactly a fixed number of items. This…
arXiv:2609.26769v1 Announce Type: cross Abstract: Decoherence free subspaces are a steady-state structure of the open quantum system which preserves quantum coherence between the states lying with in it and thus has…
arXiv:2609.26757v1 Announce Type: new Abstract: Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order…
arXiv:2609.26778v1 Announce Type: cross Abstract: Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the…
Showing 1 day · 65 items available
