Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
70 articles · 3 sources · 70 papers ·
Top topics: Algorithms
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…
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.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: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.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.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.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.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: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.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: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.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.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.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.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.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: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.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: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.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…
Showing 1 day · 70 items available
