Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
56 articles · 3 sources · 56 papers ·
Top topics: Algorithms · AI
arXiv:2609.36361v1 Announce Type: cross Abstract: In spatial matching markets, a supply unit's flexibility is measured by its service radius, the maximum distance at which it can serve demand. In dimensions $k \geq 2$,…
arXiv:2609.37483v1 Announce Type: cross Abstract: Analyses of dual lattice attacks have often assumed that the individual scores associated with short dual vectors are mutually independent. Laarhoven-Walter used this…
arXiv:2609.38101v1 Announce Type: new Abstract: We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $\kappa$,…
arXiv:2507.19417v3 Announce Type: replace-cross Abstract: It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular…
arXiv:2609.37342v1 Announce Type: new Abstract: Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the…
arXiv:2609.37118v1 Announce Type: cross Abstract: We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the…
arXiv:2609.35840v1 Announce Type: cross Abstract: We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix $A\in\mathbb{R}^{m\times n}$, at…
arXiv:2609.36311v1 Announce Type: cross Abstract: In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the…
arXiv:2609.35803v1 Announce Type: cross Abstract: We study single-agent combinatorial contracts under linear payments. Under a reward share $\alpha\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions,…
arXiv:2609.35798v1 Announce Type: new Abstract: We study statistical estimation on implicit weighted similarity graphs presented as node-arrival streams. Previous work~\cite{LZ26b} obtained constant-pass,…
arXiv:2609.36778v1 Announce Type: new Abstract: The Reduced Ordered Binary Decision Diagram (ROBDD) is a canonical representation of Boolean functions and is widely used in tasks such as equivalence checking and…
arXiv:2609.37929v1 Announce Type: new Abstract: Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing…
arXiv:2604.10857v2 Announce Type: replace-cross Abstract: Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing…
arXiv:2604.11388v5 Announce Type: replace Abstract: We consider a generalization of the Min-Sum Set Cover to the setup with $m$ set-sequences, or in scheduling terminology, $m$ parallel machines. We call this problem…
arXiv:2609.30992v2 Announce Type: replace Abstract: We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$ on compact input: distinct residues with multiplicities. It reports…
arXiv:2609.10496v2 Announce Type: replace Abstract: We design 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.37979v1 Announce Type: new Abstract: If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational…
arXiv:2608.00451v4 Announce Type: replace Abstract: We study when statistically learnable latent structure can also be recovered efficiently, and how membership queries change the answer. An unknown support…
arXiv:2609.36464v1 Announce Type: cross Abstract: The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known…
arXiv:2609.37913v1 Announce Type: cross Abstract: Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but…
Showing 1 day · 56 items available
