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.12289v1 Announce Type: new Abstract: We present a slightly simplified analysis of the asymmetric palette sparsification result by Assadi and Yazdanyar [TheoretiCS, 2026]. The motivation is mainly pedagogical;…
arXiv:2608.11858v1 Announce Type: new Abstract: We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown.…
arXiv:2509.20183v3 Announce Type: replace-cross Abstract: We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have…
arXiv:2608.12171v1 Announce Type: new Abstract: We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a…
arXiv:2608.11346v1 Announce Type: new Abstract: We prove a tight $\Theta(n/\epsilon)$ lower bound on the number of samples required for testing halfspaces over $\mathbb{R}^n$, in the distribution-free sample-based model…
arXiv:2606.03991v3 Announce Type: replace Abstract: We prove that the Grothendieck constant $K_G < \frac{\pi}{2 \log (1+ \sqrt{2})} - 10^{-5}$. This improves on the work of Braverman, Makarychev, Makarychev, and Naor…
arXiv:2607.24043v2 Announce Type: replace Abstract: We prove an elementary yet powerful combinatorial lemma: in any rooted tree with $L$ leaves, the number of nodes whose depth is smaller than the number of their leaf…
arXiv:2608.12115v1 Announce Type: new Abstract: This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle…
arXiv:2608.11158v2 Announce Type: replace-cross Abstract: We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6\pi}{11} \le K_G \le \frac{\pi}{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower…
arXiv:2608.12087v1 Announce Type: cross Abstract: This paper investigates a parallel machine scheduling problem featuring a single common server responsible for both loading and unloading operations. Each job consists…
arXiv:2608.12075v1 Announce Type: new Abstract: Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns…
arXiv:2608.08291v2 Announce Type: replace Abstract: By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two;…
arXiv:2608.11720v1 Announce Type: new Abstract: We prove that any distributed quantum algorithm that finds a $3$-coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it…
arXiv:2608.12176v1 Announce Type: new Abstract: We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a…
arXiv:2608.11413v1 Announce Type: new Abstract: The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists…
arXiv:2604.16030v5 Announce Type: replace Abstract: The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks…
arXiv:2512.25033v3 Announce Type: replace Abstract: The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in…
arXiv:2608.07352v2 Announce Type: replace Abstract: We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set $H$ via a…
arXiv:2608.12224v1 Announce Type: new Abstract: Minimizing the weighted completion times ($P \mid \mid \Sigma w_j C_j$) and weighted number of tardy jobs ($P \mid \mid \Sigma w_j U_j$) on multiple identical machines are…
arXiv:2503.00798v3 Announce Type: replace-cross Abstract: A graph $H$ is an \emph{induced minor} of a graph $G$ if $H$ can be obtained from $G$ by a sequence of edge contractions and vertex deletions. Otherwise, $G$ is…
arXiv:2608.11930v1 Announce Type: cross Abstract: For a graph $G$, its vertex deck is the multiset of graphs obtained by deleting one vertex. Bowler, Brown, and Fenner (BBF) proposed $2\lfloor(n-1)/3\rfloor$ as the…
arXiv:2608.10874v2 Announce Type: replace Abstract: A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every…
arXiv:2608.11230v1 Announce Type: cross Abstract: This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories.…
arXiv:2608.12053v1 Announce Type: new Abstract: The Gold Grabbing Game is a combinatorial game on vertex-weighted graphs in which two players alternately remove vertices while maintaining graph connectivity, aiming to…
arXiv:2601.19043v2 Announce Type: replace-cross Abstract: In 1986, Csima and F\"uredi determined the minimum number of arcs required to partition the points of Galois projective planes $PG(2,q)$ and affine planes…
arXiv:2301.00434v5 Announce Type: replace-cross Abstract: Here we merge the two fields of Cops and Robbers and Graph Pebbling to introduce the new topic of Cops and Robbers Pebbling. Both paradigms can be described by…
arXiv:2608.12039v1 Announce Type: new Abstract: We study a planar variant of the search and rescue problem whereby an agent starting at an arbitrary position $P_{\theta,r} = (r\cos\theta, r\sin\theta)$ in the plane must…
arXiv:2606.15606v2 Announce Type: replace Abstract: This paper presents several lemmas on the structure of temporal connectivity in temporal graphs. Some of these lemmas are adapted from the literature on gossip from…
arXiv:2608.11289v1 Announce Type: new Abstract: A graph $G$ is called $CIS$ if each maximal clique intersects each maximal stable set of $G$, with maximality taken with respect to set inclusion. CIS graphs resemble…
arXiv:2608.12134v1 Announce Type: cross Abstract: We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an…
arXiv:2608.11362v1 Announce Type: new Abstract: The computability of real numbers and functions using Turing Machines has been a central area of theoretical computer science since the mid-20th century. In the late 20th…
arXiv:2608.11320v1 Announce Type: new Abstract: A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\colon \{0,1\}^n\to\{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is…
arXiv:2603.16156v2 Announce Type: replace Abstract: We prove that there exists a deterministic configuration of Conflict Driven Clause Learning (CDCL) SAT solvers using a variant of the VSIDS branching heuristic that…
arXiv:2608.11385v1 Announce Type: cross Abstract: Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more…
arXiv:2605.20215v2 Announce Type: replace Abstract: The theoretical existence of Busy Beaver numbers provides a new notion for decidability and corresponding heuristic for conjectures. The minimum number of states in…
