Testing Properties of Edge Distributions
arXiv:2603.22702v2 Announce Type: replace Abstract: We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of…
Daily edition · Algorithms
The daily ledger
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
arXiv:2510.15076v2 Announce Type: replace-cross Abstract: The $\ell_p$-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the $\ell_1$-norm) and ensuring…
Triangle-Free Coloring in LOCAL via Resilient Lov\'asz Local Lemma
arXiv:2608.13357v1 Announce Type: cross Abstract: The Lov\'asz Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the…
Asymptotically Faster Algorithms for Recognizing $(k,\ell)$-Sparse Graphs
arXiv:2604.13025v2 Announce Type: replace Abstract: The family of $(k,\ell)$-sparse graphs, introduced by Lorea, plays a central role in combinatorial optimization and has a wide range of applications, particularly in…
Unlocking Fractional Moments in Delphic Set Streams
arXiv:2608.13126v1 Announce Type: new Abstract: We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption:…
New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
arXiv:2005.10800v3 Announce Type: replace Abstract: In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a…
Satisfactory Budget Division
arXiv:2502.00484v2 Announce Type: replace-cross Abstract: A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an…
Tight Adaptive Bounds for Convex Hulls
arXiv:2512.06559v2 Announce Type: replace-cross Abstract: Adaptive sorting algorithms exploit existing order in the input to obtain better-than-worst-case running times. A classical example is sorting by runs: if the…
The Cost of Changing Edges for Diameter Computation and More
arXiv:2608.12628v1 Announce Type: new Abstract: The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to…
Bagging Robustly Learns VC Classes with Linear Sample Complexity
arXiv:2608.13514v1 Announce Type: cross Abstract: We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample…
A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
arXiv:2608.13318v1 Announce Type: new Abstract: In restricted assignment - makespan minimization where each job has one size and a set of allowed machines - the configuration LP is the tightest studied relaxation, and…
Sublinear Time Eigenvector Approximation via Column Sampling
arXiv:2608.00840v2 Announce Type: replace Abstract: We study sublinear time sampling methods for approximating the outlying eigenvectors of large matrices. Our main result is an algorithm that uniformly samples just…
Efficient Randomized LL/SC that Preserves History Independence
arXiv:2608.12946v1 Announce Type: cross Abstract: We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base…
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
arXiv:2608.12503v1 Announce Type: new Abstract: We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a…
Solving Square-Submatrix Equation Systems
arXiv:2608.13408v1 Announce Type: new Abstract: We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of…
Online balancing of vectors with small coordinates
arXiv:2608.12490v1 Announce Type: cross Abstract: Let $v_1,\ldots,v_T\in B_2^m$ be fixed in advance and revealed sequentially, and assume that $\|v_t\|_\infty\leqslant d^{-1/2}$ for some $d\geqslant 1$ and every…
$\tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive Closure
arXiv:2608.13231v1 Announce Type: new Abstract: A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In…
From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures
arXiv:2608.13033v1 Announce Type: new Abstract: The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security.…
Three trees suffice for a constant stretch in minor-free graphs
arXiv:2608.13508v1 Announce Type: new Abstract: In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the…
Defensive Boosting for Online Probabilistic Forecasting
arXiv:2608.13554v1 Announce Type: cross Abstract: We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we…
An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
arXiv:2605.10058v2 Announce Type: replace Abstract: In the 2-Vertex-Connected Spanning Subgraph problem (2-VCSS), we are given an undirected graph $G$, and the objective is to find a 2-vertex-connected spanning subgraph…
Compact Path Representation in DAGs via Colored Edge Pebbling
arXiv:2608.13480v1 Announce Type: new Abstract: Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and…
Lindbladian Simulation with Commutator Bounds
arXiv:2603.28602v2 Announce Type: replace-cross Abstract: Trotter decomposition provides a simple approach to simulating open quantum systems by decomposing the Lindbladian into a sum of individual terms. While it is…
Arithmetic Variable LogLog: Advancing the Memory-Variance Frontier
arXiv:2608.12575v1 Announce Type: new Abstract: Cardinality estimation - counting the number of distinct elements in a data stream - requires a tradeoff between memory and accuracy. ExaLogLog recently established the…
Minimum eccentricity shortest paths of $K_{2,3}$-minor-free graphs
arXiv:2608.13158v1 Announce Type: new Abstract: Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether…
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
arXiv:2603.05358v2 Announce Type: replace-cross Abstract: For a fixed graph class $\Pi$, the goal of $\Pi$-Modification is to transform an input graph $G$ into a graph $H\in\Pi$ using at most $k$ modifications. Vertex…
Patching leaky tunnels in BWTs
arXiv:2608.01387v2 Announce Type: replace Abstract: We extend Baier's foundationial work on tunnelling Burrows-Wheeler Transforms (BWTs) by showing how something that would be a good tunnel except for a strings that…
Hit-and-Run Mixes as Fast as the Ball Walk
arXiv:2608.13487v1 Announce Type: new Abstract: Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance…
A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens
arXiv:2608.13130v1 Announce Type: cross Abstract: We consider the problem of shifting two tokens placed on nonadjacent vertices $u,v$ of a graph $G$ on $n$ vertices to two nonadjacent vertices $u',v'$ of $G$ using a…
On the Gap of Finite Posets
arXiv:2608.12678v1 Announce Type: cross Abstract: Let $P$ be a finite nonempty poset with $n$ elements, let $f:P\to\{1,\ldots,n\}$ be a uniformly random order-preserving bijection, and put $h_P(x)=\mathbb E[f(x)]$.…
On the Structure of $(\min,+)$ Convolution
arXiv:2608.13310v1 Announce Type: cross Abstract: The $(\min,+)$ convolution is a central problem in fine-grained complexity, and whether it admits a truly subquadratic algorithm remains open. We study it through…
A relaxation of the Bermond-Thomassen conjecture
arXiv:2608.12948v1 Announce Type: cross Abstract: The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint directed cycles. Despite being…
Quasicrystalline Gibbs states in 4-dimensional lattice-gas models with finite-range interactions
arXiv:2512.24436v2 Announce Type: replace-cross Abstract: We construct a four-dimensional lattice-gas model with finite-range interactions that has non-periodic, "quasicrystalline" Gibbs states at low temperatures. Such…
Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries
arXiv:2608.12430v1 Announce Type: new Abstract: In phylogenetics, Metropolis-Hastings methods are commonly used to sample phylogenetic trees or networks, for example from Bayesian posteriors. These methods generally use…
Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains
arXiv:2307.13826v5 Announce Type: replace Abstract: This monograph is an exposition on an exciting new technique known as spectral independence, which has been instrumental in analyzing the convergence rate of Markov…
Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students
arXiv:2608.12976v1 Announce Type: new Abstract: This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove…
Euclidean SVP is deterministically NP-hard to approximate within any constant factor
arXiv:2608.12664v1 Announce Type: new Abstract: We prove that, for every constant $\rho>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $\rho$ under a deterministic…
PSPACE-Completeness of Multi-Agent Path Finding for Large Agents
arXiv:2608.12955v1 Announce Type: new Abstract: Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in…
Long-Horizon AI Research for Grothendieck Constant: A Case Study in Human-AI Mathematical Collaboration
arXiv:2608.11195v2 Announce Type: replace-cross Abstract: AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of…
On the Expressive Power of Transformers
arXiv:2608.12671v1 Announce Type: cross Abstract: Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational…
On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation
arXiv:2608.12550v1 Announce Type: new Abstract: Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
arXiv:2608.13382v1 Announce Type: cross Abstract: Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in…