Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
113 articles · 3 sources · 113 papers ·
Top topics: Algorithms · AI
arXiv:2611.05982v1 Announce Type: new Abstract: Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts.…
arXiv:2301.03084v4 Announce Type: replace Abstract: Binary search trees (BSTs) are one of the most basic and widely used data structures. The best static tree for serving a sequence of queries (searches) can be computed…
arXiv:2607.26630v2 Announce Type: replace Abstract: In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of…
arXiv:2611.05598v1 Announce Type: new Abstract: We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is…
arXiv:2610.31513v3 Announce Type: replace Abstract: We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the…
arXiv:2611.05878v1 Announce Type: new Abstract: Given an undirected unweighted graph $G$ on $n$ vertices and a set $P$ of $p$ pairs of its vertices, a distance preserver is a sparse subgraph of $G$ that exactly…
arXiv:2505.07681v5 Announce Type: replace-cross Abstract: We present OCaml and Rocq implementations of Kaplan and Tarjan's purely functional, real-time catenable deques. The correctness of our Rocq code is…
arXiv:2502.14379v3 Announce Type: replace-cross Abstract: We study the problem of $K$-armed bandits with reward distributions belonging to a one-parameter exponential distribution family. In the literature, several…
arXiv:2611.05712v1 Announce Type: new Abstract: The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name,…
arXiv:2611.06611v1 Announce Type: new Abstract: We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $\epsilon>0$, the algorithm maintains a…
arXiv:2611.06615v1 Announce Type: cross Abstract: We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance $\Sigma$ is…
arXiv:2605.14994v2 Announce Type: replace-cross Abstract: We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$.…
arXiv:2611.06482v1 Announce Type: new Abstract: In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and…
arXiv:2611.05932v1 Announce Type: new Abstract: We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions…
arXiv:2611.05725v1 Announce Type: new Abstract: \emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute…
arXiv:2611.06896v1 Announce Type: new Abstract: We give a $0.556195$-competitive randomized algorithm for edge-weighted online bipartite matching with free disposal, improving the $0.5368$ guarantee of Blanc and…
arXiv:2602.09497v3 Announce Type: replace Abstract: We study the maintenance of a $(\Delta+C)$-edge-coloring ($C\ge 1$) in a fully dynamic graph $G$ with maximum degree $\Delta$. We focus on minimizing \emph{recourse}…
arXiv:2609.17655v3 Announce Type: replace Abstract: In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a…
arXiv:2607.07934v2 Announce Type: replace Abstract: The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively…
arXiv:2611.06626v1 Announce Type: new Abstract: How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic…
Showing 1 day · 113 items available
