Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
68 articles · 3 sources · 68 papers ·
Top topics: Algorithms · AI
arXiv:2611.13600v1 Announce Type: cross Abstract: We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but…
arXiv:2610.01311v2 Announce Type: replace Abstract: The weighted edit distance $\mathsf{ed}^w(X,Y)$ is the minimum cost of an alignment of strings $X$ and $Y$, where a weight function $w$ specifies the cost of each…
arXiv:2610.35495v2 Announce Type: replace Abstract: This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points,…
arXiv:2611.13568v1 Announce Type: new Abstract: Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask…
arXiv:2611.13984v1 Announce Type: new Abstract: We give a deterministic $O(n+k^2)$-time algorithm for bounded weighted edit distance when the input costs form an integer metric on the alphabet extended by a gap symbol.…
arXiv:2611.13750v1 Announce Type: new Abstract: We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum…
arXiv:2611.13392v1 Announce Type: new Abstract: The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate…
arXiv:2609.37431v2 Announce Type: replace Abstract: We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query…
arXiv:2611.13757v1 Announce Type: new Abstract: We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of…
arXiv:2611.13635v1 Announce Type: new Abstract: This paper studies complete Min-$k$-CSPs: an instance on $n$ variables has one nontrivial constraint for every $k$-set of variables (so $\binom{n}{k}$ constraints in…
arXiv:2611.14342v1 Announce Type: new Abstract: Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we…
arXiv:2611.14163v1 Announce Type: new Abstract: The binary rank of a binary matrix is the minimum number of disjoint all-one rectangles that partition its one-entries. We study entry-query testing of binary rank at most…
arXiv:2610.25955v2 Announce Type: replace Abstract: We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\…
arXiv:2604.10819v3 Announce Type: replace Abstract: A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying…
arXiv:2611.13294v1 Announce Type: new Abstract: In the Function Inversion problem, the goal is to invert a function $f:[N] \to [N]$ in two phases. In the preprocessing phase, the offline algorithm computes an advice…
arXiv:2611.13585v1 Announce Type: new Abstract: We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most $\frac{89}{64}=\frac{7}{5}-\frac{3}{320}$ times the value of the subtour…
arXiv:2606.18048v5 Announce Type: replace-cross Abstract: A foundational theorem of Ajtai, Koml\'os, Pintz, Spencer, and Szemer\'edi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph (i.e., with girth at…
arXiv:2611.14513v1 Announce Type: new Abstract: We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $\Omega(n / \log^2 n)$ for both deterministic and…
arXiv:2611.13980v1 Announce Type: new Abstract: We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time.…
arXiv:2606.23727v3 Announce Type: replace-cross Abstract: The matrix of single- and two-qubit Pauli-Z expectation values of any quantum state is the moment matrix of its computational-basis outcome distribution; it…
Showing 1 day · 68 items available
