Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
87 articles · 3 sources · 87 papers ·
Top topics: Algorithms · AI
arXiv:2610.00547v1 Announce Type: cross Abstract: We establish functional aggregate queries (FAQs) as a unifying language for exact classical simulation of quantum circuits. A circuit becomes a sum-product query:…
arXiv:2610.00177v1 Announce Type: new Abstract: In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of…
arXiv:2609.35668v2 Announce Type: replace-cross Abstract: We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is…
arXiv:2610.01071v1 Announce Type: new Abstract: We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors,…
arXiv:2610.00310v1 Announce Type: new Abstract: In the designer-port routing-labeling problem, every vertex of a rooted tree receives a binary label and the child edges receive distinct port numbers. Given only the…
arXiv:2604.27651v2 Announce Type: replace Abstract: For a connected weighted hypergraph, we give a randomized almost-linear-time solver for the Poisson problem for the cut-based hypergraph Laplacian in the natural input…
arXiv:2610.02008v1 Announce Type: cross Abstract: Kikuchi matrices are a family of structured matrices that were introduced to study problems involving tensors and hypergraphs. We show that, as the ambient dimension…
arXiv:2610.01591v1 Announce Type: new Abstract: We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin…
arXiv:2607.07153v2 Announce Type: replace-cross Abstract: We study ranking and rank aggregation under the Kendall tau distance, subject to matroid or flag matroid constraints on prefixes of the output ranking. In the…
arXiv:2610.02131v1 Announce Type: cross Abstract: We study linear programming (LP) representations and strongly polynomial algorithms for robust Markov decision processes (RMDPs) with rational polyhedral state-action…
arXiv:2610.00577v1 Announce Type: new Abstract: In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality…
arXiv:2606.13583v2 Announce Type: replace Abstract: The seminal work of Goldreich and Ron (\textit{Combinatorica, 1999}) showed that bipartiteness of bounded-degree graphs can be tested using $O(\sqrt{n\log n})$ random…
arXiv:2610.01007v1 Announce Type: new Abstract: In the streaming set cover problem, $m$ sets from a universe of size $n$ are arriving one by one in a stream, and the algorithm is allowed to process the stream using one…
arXiv:2610.02079v1 Announce Type: cross Abstract: We study the transverse field Ising model, defined by the Hamiltonian $H =\frac{1}{2}\sum_{i, j\in [n]} J_{ij} Z_i Z_j +\sum_{i=1}^n h_i^z Z_i + \eta\sum_{i} X_i$ where…
arXiv:2610.00103v1 Announce Type: cross Abstract: We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival.…
arXiv:2607.28260v2 Announce Type: replace-cross Abstract: Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$…
arXiv:2610.01853v1 Announce Type: new Abstract: In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for $\texttt{rank}/\texttt{select}$ operations. Using the standard…
arXiv:2610.01902v1 Announce Type: cross Abstract: Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as…
arXiv:2609.18707v2 Announce Type: replace Abstract: Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance…
arXiv:2609.38736v1 Announce Type: cross Abstract: Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those…
Showing 1 day · 87 items available
