Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
45 articles · 3 sources · 45 papers ·
Top topics: Algorithms · AI
arXiv:2610.32298v2 Announce Type: replace Abstract: The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an…
arXiv:2610.37630v1 Announce Type: cross Abstract: We give algorithms for approximating the partition function $Z_N$ of the Sherrington--Kirkpatrick (SK) model and finite mixed Ising $p$-spin models with $p\ge 3$. The…
arXiv:2610.37295v1 Announce Type: new Abstract: A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within…
arXiv:2507.16648v3 Announce Type: replace-cross Abstract: We prove that, for every fixed $\epsilon\in(0,1]$, the active-set method requires exponentially many iterations in the worst case to maximize a convex objective…
arXiv:2610.28930v3 Announce Type: replace Abstract: We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $[N]$, where…
arXiv:2607.18220v2 Announce Type: replace-cross Abstract: We study the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) beyond additive valuations. For two agents with monotone submodular…
arXiv:2411.07030v4 Announce Type: replace-cross Abstract: We study the \emph{Polynomial Avoidance Problem}: given a finite collection $F \subseteq Z[x_1,\dots,x_n]$ of nonzero polynomials, find a vector $x \in Z^n$ of…
arXiv:2610.37018v1 Announce Type: new Abstract: A planar graph is rectilinear planar if it admits a planar orthogonal drawing without bends. For series-parallel graphs in the variable embedding setting the best known…
arXiv:2610.37361v1 Announce Type: new Abstract: We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked,…
arXiv:2607.27264v2 Announce Type: replace-cross Abstract: A tree cover of an $n$-point metric space is a collection of $k$ trees such that every pairwise distance is approximately preserved in at least one tree. For…
arXiv:2610.29624v2 Announce Type: replace Abstract: An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of…
arXiv:2610.23364v2 Announce Type: replace Abstract: Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$. Estimating $m$ from uniformly random hyperedge samples requires $\Theta(\sqrt{m})$ samples by a…
arXiv:2608.18577v3 Announce Type: replace Abstract: We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting…
arXiv:2610.30776v2 Announce Type: replace-cross Abstract: Phylogenetic distance deconvolution represents mixture-to-reference distances by weighted sources placed on a reference tree. We study the minimum number of…
arXiv:2610.36577v1 Announce Type: new Abstract: We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model.…
arXiv:2610.37192v1 Announce Type: new Abstract: In the generalized $k$-server problem, each of $k$ servers moves in its own metric space, and a request $(r_1,\dots,r_k)$ is served once some server $i$ stands at the…
arXiv:2610.37065v1 Announce Type: new Abstract: The mixed evacuation problem is a variant of the dynamic transshipment problem where there exist two modes of transportation and we allocate supplies to each mode of…
arXiv:2610.00920v3 Announce Type: replace Abstract: We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19],…
arXiv:2602.06860v2 Announce Type: replace Abstract: Extracting exact and complete information using range queries is not only time-inefficient, on average, but also susceptible to privacy breaches. As a remedy,…
arXiv:2610.36630v1 Announce Type: new Abstract: We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over…
Showing 1 day · 45 items available
