Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
57 articles · 3 sources · 57 papers ·
Top topics: Algorithms · AI
arXiv:2610.22278v1 Announce Type: new Abstract: We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees…
arXiv:2603.18391v2 Announce Type: replace Abstract: The distance from calibration, introduced by B{\l}asiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for…
arXiv:2608.07134v2 Announce Type: replace Abstract: Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the…
arXiv:2610.21961v1 Announce Type: new Abstract: The Preprocessed 3SUM problem asks to preprocess a set $A$ of $n$ numbers so that we can quickly decide whether a query subset $A' \subseteq A$ contains a solution…
arXiv:2610.21418v1 Announce Type: new Abstract: In a self-sizing set-reconciliation protocol, a small first-round Invertible Bloom Lookup Table (IBLT) sketch attempts peeling decoding; after failure, the protocol…
arXiv:2610.21072v1 Announce Type: new Abstract: We obtain a $0.4584$-approximation for nonnegative, non-monotone, $L$-smooth DR-submodular maximization over compact convex down-closed subsets of the unit cube, improving…
arXiv:2605.12461v3 Announce Type: replace-cross Abstract: We propose an algorithm to sample from composite log-concave distributions over $\mathbb{R}^d$, i.e., densities of the form $\pi\propto e^{-f-g}$, assuming…
arXiv:2506.01228v5 Announce Type: replace Abstract: We establish that a practical polynomial-time algorithm obtains near-optimal $\frac23$-balanced vertex separators for a number of graph classes, including genus-$g$…
arXiv:2610.20983v1 Announce Type: new Abstract: We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on $n$ values with positive weights. Preprocessing takes $O(n\log^2…
arXiv:2610.21285v1 Announce Type: new Abstract: We present a simple deterministic $O(\log n)$-competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric…
arXiv:2610.07387v2 Announce Type: replace Abstract: Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this…
arXiv:2610.22010v1 Announce Type: new Abstract: We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the…
arXiv:2605.24068v2 Announce Type: replace Abstract: This article deals with the sampling and statistics of uniform random mappings and surjections from $[n]=\{1,\ldots,n\}$ to $[k]=\{1,\ldots,k\}$. More precisely, we…
arXiv:2508.16531v3 Announce Type: replace Abstract: Many algorithms are designed to work well on average over inputs. But when such an algorithm is run on an arbitrary input, the question arises: Can we trust the…
arXiv:2610.20813v1 Announce Type: new Abstract: In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the…
arXiv:2610.21793v1 Announce Type: cross Abstract: The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full…
arXiv:2610.20769v1 Announce Type: new Abstract: The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We…
arXiv:2610.22302v1 Announce Type: new Abstract: In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$-matrix so that all row and column sums are $1$. We provide a…
arXiv:2610.03030v2 Announce Type: replace Abstract: The matroid parity problem generalizes both graph matching and matroid intersection. Although the general version is intractable, Lov\'asz (1981) developed a…
arXiv:2610.21033v1 Announce Type: cross Abstract: We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by…
Showing 1 day · 57 items available
