Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
41 articles · 3 sources · 41 papers ·
Top topics: Algorithms · AI
arXiv:2609.10267v1 Announce Type: new Abstract: We study the \emph{vantage point selection} problem, introduced by Ashvinkumar, Chowdhury, Gao, Goswami, Mitchell, and Polishchuk [WADS'25] to model the problem of…
arXiv:2609.10516v1 Announce Type: new Abstract: We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a…
arXiv:2609.10496v1 Announce Type: new Abstract: We provide an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log(d+1)/\epsilon^2)$, where $d$ is the…
arXiv:2609.02978v2 Announce Type: replace Abstract: We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013):…
arXiv:2609.07862v2 Announce Type: replace Abstract: This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter permutation generation algorithm, targeted at modern x86-64…
arXiv:2609.10514v1 Announce Type: cross Abstract: We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small…
arXiv:2601.21202v3 Announce Type: replace Abstract: This paper establishes the exact comparison complexity of finding an element repeated $n$ times in a $2n$-element array containing $n+1$ distinct values, under the…
arXiv:2609.09622v1 Announce Type: new Abstract: Motivated by data produced by generative systems, \cite{LZ26b} formulates similarity-aware statistics via a weighted similarity graph, replacing equality with similarity…
arXiv:2609.09809v1 Announce Type: cross Abstract: In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general…
arXiv:2609.09524v1 Announce Type: cross Abstract: We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq \epsilon$, for a general norm $\|\cdot\|$ and a self-map $T$ of a…
arXiv:2609.09837v1 Announce Type: cross Abstract: Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes. We study the parameterized…
arXiv:2609.09701v1 Announce Type: new Abstract: We study fast algorithms for sparse-PCA certification. Given a positive semidefinite matrix $M$, the problem asks either to rule out a large $k$-sparse quadratic form or…
arXiv:2607.25973v2 Announce Type: replace Abstract: We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$.…
arXiv:2112.04169v3 Announce Type: replace-cross Abstract: We consider online resource allocation under a typical non-profit setting, where limited or even scarce resources are administered by a not-for-profit…
arXiv:2609.09427v1 Announce Type: new Abstract: We study the approximate nearest neighbor problem under $\ell_\infty$ in the ultra-high dimensional setting where the dimension $d$ is significantly larger than the number…
arXiv:2508.21667v4 Announce Type: replace-cross Abstract: Block encoding of sparse matrices underpins quantum algorithms such as quantum singular value transformation, Hamiltonian simulation, and quantum linear system…
arXiv:2609.10004v1 Announce Type: new Abstract: The 11/6 worst-case constant of the Wang-Sitters rounding scheme, which a companion note establishes, can naturally be attributed to the freedom in Step 3, where an…
arXiv:2609.09623v1 Announce Type: cross Abstract: Byzantine agreement (BA) is a foundational building block in distributed systems, and the security analysis of BA protocols under multi-instance executions has attracted…
arXiv:2510.11547v2 Announce Type: replace Abstract: Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a $k$-clustering produced by SLC can be obtained by…
arXiv:2609.08733v1 Announce Type: cross Abstract: We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state $\rho$…
Showing 1 day · 41 items available
