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:2401.15781v4 Announce Type: replace Abstract: The hereditary discrepancy of a set system is a certain quantitative measure of the pseudorandom properties of the system. Roughly, hereditary discrepancy measures how…
arXiv:2410.11090v2 Announce Type: replace-cross Abstract: Lanczos-based methods have become standard tools for tasks involving matrix functions. Progress on these algorithms has been driven by several largely disjoint…
arXiv:2608.17907v1 Announce Type: new Abstract: We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $\sigma$ to answer…
arXiv:2608.13126v2 Announce Type: replace 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…
arXiv:2608.17358v1 Announce Type: new Abstract: Recent multi-scale nearest-source methods give polynomially sublinear girth approximations in CONGEST. We isolate the direct black-box route for making this framework…
arXiv:2608.16947v1 Announce Type: new Abstract: Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is…
arXiv:2608.17990v1 Announce Type: new Abstract: The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance…
arXiv:2509.04640v3 Announce Type: replace Abstract: We present a $+2\sum_{i=1}^{k+1}{W_i}$-APASP algorithm for dense weighted graphs with runtime $\tilde O\left(n^{2+\frac{1}{3k+2}}\right)$, where $W_{i}$ is the weight…
arXiv:2608.16916v1 Announce Type: new Abstract: Calculating average distances in large-scale networks is computationally intensive and constrained by limited main memory, posing a significant challenge in graph…
arXiv:2608.03687v2 Announce Type: cross Abstract: Let $\{0, 1\}^n$ be the Boolean cube, endowed with the probability product measure, where ${\Bbb P}(1)=p$ and ${\Bbb P}(0)=q$ with $0 < p \leq q$ and $p+q=1$. For $i=1,…
arXiv:2010.07076v2 Announce Type: replace Abstract: The research on indexing repetitive string collections has focused on the same search problems used for regular string collections, though they can make little sense…
arXiv:2608.17818v1 Announce Type: cross Abstract: We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic…
arXiv:2608.17835v1 Announce Type: new Abstract: We study the parameterized complexity of $k$-Coloring in $H$-free graphs, when $H$ is a linear forest (i.e., a disjoint union of paths) as an induced subgraph. We show two…
arXiv:2602.16222v2 Announce Type: replace-cross Abstract: We investigate space-time trade-offs for population protocols in sparse interaction graphs. In complete interaction graphs, optimal space-time trade-offs are…
arXiv:2608.16944v1 Announce Type: new Abstract: Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved…
arXiv:2509.19914v3 Announce Type: replace Abstract: We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive…
arXiv:2608.17384v1 Announce Type: new Abstract: We show that the balancing weights technique of Li (2026) actually produces an approximate *pseudo-circulation* of a directed, capacitated graph in $m^{1+o(1)}$ time.…
arXiv:2511.02725v2 Announce Type: replace-cross Abstract: We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group $S_n$. In each step, an…
arXiv:2608.17294v1 Announce Type: cross Abstract: Let $Q$ be a nonzero $s\times t$ $(0,1)$-pattern, and let $m\ge s$ and $n\ge t$. An $m\times n$ matrix is strongly $Q$-forcing if every $1$-entry belongs to an $s\times…
arXiv:2603.17730v3 Announce Type: replace-cross Abstract: In recent work, Martinsson and Steiner proved that triangle-free $d$-degenerate graphs have fractional chromatic number $\chi_f(G) = O\left(\frac{d}{\log…
arXiv:2606.21298v2 Announce Type: replace Abstract: A family of permutations of $[n]$ is called setwise distinguishable if for every permutation in the family there exists a subset of $[n]$ whose image under this…
arXiv:2608.17893v1 Announce Type: new Abstract: Reaction networks model reactions between a finite set of species. These networks can be associated with different semantics, depending on the type of analysis and the…
arXiv:2608.17637v1 Announce Type: cross Abstract: For each $d\in\N_{\geq 2}$ we construct a Delone set $Y$ in $\R^{d}$ for which every Lipschitz bijection from $Y$ to $\Z^{d}$ has a very irregular inverse. For example,…
arXiv:2607.13165v4 Announce Type: replace-cross Abstract: For integer vectors R,S let A(R,S) denote the class of (0,1)-matrices with row sum vector R and column sum vector S. Its interchange graph G(R,S) has A(R,S) as…
arXiv:2608.17227v1 Announce Type: cross Abstract: Let $K_{r,s,t}$, with $r\le s\le t$, denote the complete tripartite graph whose partite sets have sizes $r,s,t$. Mahmoodian and Mirzakhani gave three necessary…
arXiv:2608.17109v1 Announce Type: cross Abstract: Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for…
arXiv:2601.18747v3 Announce Type: replace-cross Abstract: Modern AI agents increasingly rely on search infrastructure to execute complex, neuro-symbolic reasoning workflows. These workflows often compile into deeply…
arXiv:2608.18048v1 Announce Type: new Abstract: We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as…
arXiv:2608.17047v1 Announce Type: new Abstract: For every $n\geq 9$ that is a multiple of 3, we construct an explicit access structure on $n$ participants. In every perfect secret-sharing scheme realising this access…
arXiv:2608.17733v1 Announce Type: new Abstract: In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should…
arXiv:2608.17365v1 Announce Type: cross Abstract: For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a…
arXiv:2607.13630v3 Announce Type: replace-cross Abstract: We study the separation of geometric effects from quantum interference in quantum optimization algorithms. Constrained optimization problems such as routing,…
arXiv:2608.17429v1 Announce Type: new Abstract: We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication.…
arXiv:2512.16082v3 Announce Type: replace Abstract: Ben-Sasson, Goldreich and Sudan showed that a binary error correcting code admitting a $2$-query tester cannot be good, i.e., it cannot have both linear distance and…
