Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
37 articles · 3 sources · 37 papers ·
Top topics: Algorithms · AI
arXiv:2609.12777v1 Announce Type: cross Abstract: We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our…
arXiv:2609.12346v1 Announce Type: cross Abstract: To prove the quantum soundness of the classical low-individual-degree test, the authors of \cite{JNVWY20LID} defined three subtests, namely the axis-parallel lines test,…
arXiv:2609.12164v1 Announce Type: new Abstract: We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals…
arXiv:2609.12669v1 Announce Type: new Abstract: Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem.…
arXiv:2609.13032v1 Announce Type: cross Abstract: We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli,…
arXiv:2607.08908v2 Announce Type: replace-cross Abstract: In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard…
arXiv:2609.13132v1 Announce Type: new Abstract: We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong…
arXiv:2510.18260v3 Announce Type: replace Abstract: This paper proposes Warshall-type algorithms for determining connectedness and clustering in an undirected matrix-weighted graphs. While a path between two vertices…
arXiv:2609.12647v1 Announce Type: cross Abstract: Finding large lattice subgraphs in sparse Erd\H{o}s--R\'enyi random graphs is a classical problem at the interface of random graph theory and algorithms. General…
arXiv:2609.12214v1 Announce Type: cross Abstract: We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the…
arXiv:2609.08847v3 Announce Type: replace-cross Abstract: Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved…
arXiv:2609.12617v1 Announce Type: new Abstract: Johnson graphs $J(n,k)$ are a classical family of highly symmetric networks known to be Hamiltonian-connected in the fault-free setting. In this paper, we investigate…
arXiv:2507.03151v2 Announce Type: replace-cross Abstract: The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various…
arXiv:2609.12569v1 Announce Type: cross Abstract: We introduce and study the rotating-memory Fibonacci numbers, a periodic variable-order analogue of the Fibonacci sequence in which the number of preceding terms used in…
arXiv:2209.11882v3 Announce Type: replace-cross Abstract: The deletion distance between two binary words $u,v \in \{0,1\}^n$ is the smallest $k$ such that $u$ and $v$ share a common subsequence of length $n-k$. A set…
arXiv:2601.18951v2 Announce Type: replace-cross Abstract: In this paper, we consider the problem of counting almost empty monochromatic triangles in colored planar point sets, that is, triangles whose vertices are all…
arXiv:2609.12021v1 Announce Type: new Abstract: Bj\"orklund, Husfeldt, and Kaski gave a randomized $\widetilde{O}(n^{\omega+3})$-time algorithm for computing the length of a shortest even cycle in an $n$-vertex directed…
arXiv:2609.06725v2 Announce Type: replace-cross Abstract: We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower…
arXiv:2608.06796v3 Announce Type: replace Abstract: We study online multi-level aggregation on finite rooted trees with a per-batch maximum-delay objective. A service pays for a rooted subtree and for the maximum…
arXiv:2504.07133v2 Announce Type: replace-cross Abstract: We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by…
Showing 1 day · 37 items available
