Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2608.16884v1 Announce Type: new Abstract: The current best bounds on the matrix multiplication exponent $\omega$ are obtained through a refinement of the laser method called combination loss analysis (Duan et al.,…
arXiv:2604.10819v2 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:2608.15836v1 Announce Type: new Abstract: In this paper, the recoverable robust representative selection problem is considered, where uncertain second-stage costs are modeled using interval uncertainty with a…
arXiv:2608.16315v1 Announce Type: new Abstract: Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor…
arXiv:2605.07386v2 Announce Type: replace-cross Abstract: \emph{Convex Optimization with Nested Evolving Feasible Sets (CONES)} is considered where the objective function \(f\) remains fixed but the feasible region…
arXiv:2602.16240v3 Announce Type: replace Abstract: Motivated by a wide range of applications in data mining and machine learning, we consider the problem of maximizing a submodular function subject to supermodular cost…
arXiv:2608.16382v1 Announce Type: new Abstract: We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic…
arXiv:2602.14748v2 Announce Type: replace-cross Abstract: For a fixed regular language $L$, the enumeration of $L$-infixes is the following task: we are given an input word $w = a_1 \cdots a_n$ and we must enumerate the…
arXiv:2608.15390v1 Announce Type: new Abstract: Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that…
arXiv:2608.15822v1 Announce Type: cross Abstract: The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting,…
arXiv:2607.15260v2 Announce Type: replace Abstract: What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of…
arXiv:2608.16359v1 Announce Type: new Abstract: In this paper, we address several problems concerning vector spaces enclosed in a given set. Let V be a vector space over a finite field of cardinality c, and let $S…
arXiv:2608.10193v2 Announce Type: replace-cross Abstract: We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on…
arXiv:2608.15172v1 Announce Type: cross Abstract: In apparel retail and other applications, when a customer's preferred size is unavailable, demand may shift to nearby sizes. This substitution creates new assortment and…
arXiv:2608.16123v1 Announce Type: new Abstract: Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{supp}(A \star B)|$. We give a Las Vegas algorithm that computes $A \star B$ in $O(t…
arXiv:2606.17215v2 Announce Type: replace-cross Abstract: A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean…
arXiv:2607.23787v2 Announce Type: replace Abstract: In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more…
arXiv:2606.23556v3 Announce Type: replace Abstract: We consider expectations of the type $E \exp \left\{\sum_{i=1}^m \phi_i \right\}$, where $\phi_i: {\Bbb R}^n \longrightarrow {\Bbb C}$ are functions, each depending on…
arXiv:2608.15954v1 Announce Type: cross Abstract: Burning is a discrete-time model for propagation in which a new fire starts in each round, while each existing fire expands by one unit of distance along the underlying…
arXiv:2305.00979v4 Announce Type: replace-cross Abstract: Gaussian mixture block models are distributions over graphs that strive to model modern networks: to generate a graph from such a model, we associate each vertex…
arXiv:2608.15159v1 Announce Type: new Abstract: We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time,…
arXiv:2608.15328v1 Announce Type: new Abstract: If a table violates its required set of functional dependencies (FDs), what is the minimum number of cell changes needed to restore consistency? This fundamental problem,…
arXiv:2605.10058v3 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…
arXiv:2608.16878v1 Announce Type: new Abstract: For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $\Omega(1/(n^2 C_{\mathsf{PI}}))$, where…
arXiv:2608.15496v1 Announce Type: new Abstract: We study the problem of minimizing total weighted completion time on unrelated parallel machines with machine-independent job weights. The best previous approximation…
arXiv:2604.00724v3 Announce Type: replace Abstract: We obtain better algorithms for computing more balanced orientations and degree splits in LOCAL. Important to our result is a connection to the hypergraph sinkless…
arXiv:2608.16298v1 Announce Type: new Abstract: Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis…
arXiv:2608.16339v1 Announce Type: new Abstract: Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering…
arXiv:2608.16109v1 Announce Type: cross Abstract: We study fair division of indivisible goods when agents' valuations are accessed only through ordinal comparisons between bundles, with arbitrary tie-breaking. In this…
arXiv:2608.16615v1 Announce Type: new Abstract: In the replacement paths (RP) problem, we are given a graph $G = (V, E)$ with $n = |V|$ and $m = |E|$, together with two vertices $s, t \in V$, and are asked to compute…
arXiv:2604.04137v2 Announce Type: replace-cross Abstract: The Grover lower bound for the unstructured search problem can be surpassed when some information about the data structure is available. Here, we numerically…
arXiv:2607.06968v2 Announce Type: replace Abstract: We show how to visualize a graph, $G=(V,E)$, as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of…
arXiv:2104.04908v2 Announce Type: replace Abstract: We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and…
arXiv:2505.00922v3 Announce Type: replace Abstract: The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition…
arXiv:2608.09191v2 Announce Type: replace-cross Abstract: For an edge $uv$ of a finite simple graph $G$, its imbalance is $|d_G(u)-d_G(v)|$, and the imbalance multiset $M_G$ consists of the imbalances of all edges of…
arXiv:2607.26894v3 Announce Type: replace-cross Abstract: Many real-life systems can be found as examples of stochastic matching on hypergraphs, such as production lines or assemble-to-order systems. Two common features…
arXiv:1910.04162v4 Announce Type: replace Abstract: We develop the mathematical theory of a model, constructed by C. Gu, I. Downes, O. Gnawali, and L. Guibas, of networks that diffuse continuously acquired information…
arXiv:2608.16861v1 Announce Type: new Abstract: We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the…
arXiv:2607.07688v4 Announce Type: replace-cross Abstract: How close to singularity can an $n \times n$ unimodular matrix be? For ternary cases as $n$ increases, exact expressions are unlikely, but upon fixing $n=4$ and…
arXiv:2209.06404v2 Announce Type: replace-cross Abstract: We establish a three-dimensional analogue of the classical theorem that a Latin square of order \(m\) can be embedded in a Latin square of order \(n\) if and…
arXiv:2306.07862v3 Announce Type: replace Abstract: In this paper, we broaden the understanding of the recently introduced concepts of solid-locating-dominating and self-locating-dominating codes in various graphs. In…
arXiv:2608.14687v1 Announce Type: cross Abstract: The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex…
arXiv:2608.15724v1 Announce Type: cross Abstract: The frequency $K_i$s ($i\in[4,n]$) are studied for symmetric traveling salesman problem ($TSP$) to characterize the structure properties of the edges inside and outside…
arXiv:2606.25988v2 Announce Type: replace-cross Abstract: We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every…
arXiv:2608.15670v1 Announce Type: cross Abstract: We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based…
arXiv:2605.28570v2 Announce Type: replace-cross Abstract: We prove that every concatenation of $10$ or more binary squares contains an overlap. The bound $10$ is best possible. In contrast, over a ternary alphabet,…
arXiv:2608.14695v1 Announce Type: cross Abstract: An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it.…
arXiv:2608.16777v1 Announce Type: cross Abstract: Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting…
arXiv:2509.06692v3 Announce Type: replace-cross Abstract: We study the problem of correcting pairwise disjoint adjacent transpositions (or swaps) in $q$-ary strings. Equivalently, the model we assume is the radius-one…
arXiv:2608.16090v1 Announce Type: cross Abstract: Discrete Convex Analysis (DCA) is a discrete analog of continuous convex analysis, originally proposed as a unified theoretical framework for efficiently solvable…
arXiv:2608.15398v1 Announce Type: cross Abstract: The generalized pancake graph $P(m,n)$ is the Cayley graph of the group of colored permutations $\mathbb{Z}_m\wr S_n=(\mathbb{Z}_m)^n\rtimes S_n$ generated by…
arXiv:2506.01467v4 Announce Type: replace-cross Abstract: Graph generative models perform well on small-scale structured data but struggle to scale to large, complex structures. Hierarchical approaches improve…
arXiv:2608.14817v1 Announce Type: cross Abstract: For each $N\geq1$, consider the normalized K\"onig bilinear form $B_{\mathrm K}:L_\infty(\mathbb R^N)\times L_\infty(\mathbb R^N)\to\mathbb R$ given by \[ B_{\mathrm…
arXiv:2504.05191v2 Announce Type: replace-cross Abstract: In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL…
arXiv:2608.16438v1 Announce Type: cross Abstract: In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but…
arXiv:2608.15184v1 Announce Type: cross Abstract: This paper is a failure analysis of the representation layer underlying GNN-based smart contract vulnerability detectors. These systems convert source code into graphs…
arXiv:2608.16682v1 Announce Type: cross Abstract: Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price…
arXiv:2608.16854v1 Announce Type: new Abstract: We show that, on trees, any locally checkable labeling problem (LCL) $\Pi$ that can be solved by an $n^{o(1)}$-dependent distribution can also be solved by an $O(\log…
arXiv:2608.14529v2 Announce Type: replace Abstract: For every constant $2 <\infty$ and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the $\ell_p$-shortest vector problem for…
arXiv:2608.14845v1 Announce Type: new Abstract: In a landmark JACM paper recognized with the 2021 G{\"o}del Prize, Cai and Chen established a complete complexity dichotomy for counting CSPs over arbitrary finite domains…
arXiv:2608.16857v1 Announce Type: cross Abstract: We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we…
arXiv:2404.10380v2 Announce Type: replace Abstract: We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D platforming video game series. Previously, only the original Super Mario Bros. was known to be…
arXiv:2608.16150v1 Announce Type: new Abstract: Input-convex neural networks permit globally tractable minimization over their inputs, so one might expect their global regularity to be tractable in low input dimension.…
arXiv:2608.14975v1 Announce Type: new Abstract: \emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense…
arXiv:2608.16860v1 Announce Type: new Abstract: We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are…
arXiv:2608.16649v1 Announce Type: new Abstract: The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how…
arXiv:2608.15847v1 Announce Type: new Abstract: We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in…
arXiv:2608.10696v2 Announce Type: replace Abstract: Shellsort repeatedly runs insertion sort with decreasing gaps, so its worst-case cost depends on the gap sequence. Pratt's $2^u3^v$ sequence, one of the few systematic…
arXiv:2405.10546v2 Announce Type: replace Abstract: We prove RE-completeness (and thus undecidability) of several 2D games in the Super Mario Bros. platform video game series: the New Super Mario Bros. series (original,…
arXiv:2608.15937v1 Announce Type: cross Abstract: In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq \Sigma^N$ and a received word $y \in \Sigma^N$, find…
