Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
57 articles · 3 sources · 57 papers ·
Top topics: Algorithms · AI
arXiv:2603.00210v2 Announce Type: replace Abstract: Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to…
arXiv:2404.04599v4 Announce Type: replace-cross Abstract: We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one…
arXiv:2609.17914v1 Announce Type: new Abstract: For a constraint satisfaction problem defined by a relation $R$, its non-redundancy $\text{NRD}(R,n)$ is the size of largest instance (as a function of the number $n$ of…
arXiv:2604.01519v2 Announce Type: replace-cross Abstract: We study the computational complexity of estimating the normalized trace $2^{-n}\mathrm{Tr}[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This…
arXiv:2609.18692v1 Announce Type: new Abstract: In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of…
arXiv:2609.18261v1 Announce Type: cross Abstract: We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library…
arXiv:2609.18484v1 Announce Type: new Abstract: We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit…
arXiv:2609.18807v1 Announce Type: cross Abstract: Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds…
arXiv:2607.26139v2 Announce Type: replace-cross Abstract: Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for…
arXiv:2306.06224v2 Announce Type: replace-cross Abstract: Hadwiger's Conjecture asserts that every $K_h$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger's…
arXiv:2603.20947v2 Announce Type: replace-cross Abstract: We study the adjacency spectra of zero-divisor graphs associated with Lipschitz quaternion rings modulo $n$. For an odd prime $p$, the identification…
arXiv:2609.18331v1 Announce Type: cross Abstract: Backman and Liu proved that every integral generalized permutohedron of type $A$, and in particular every matroid base polytope, admits a regular unimodular…
arXiv:2609.17877v1 Announce Type: cross Abstract: We present an exposition of a proof, discovered by GPT-6 Astra, of the Erd\H{o}s--S\'os Conjecture, which states that every graph with average degree greater than $t-2$…
arXiv:2506.19529v3 Announce Type: replace Abstract: The concept of domination in graphs plays a central role in understanding structural properties and applications in network theory. In this study, we focus on the…
arXiv:2609.18318v1 Announce Type: cross Abstract: We use $m$-dimensional partial spreads of $\fp^{2n}$, where $p$ is an odd prime, $n$ is a positive integer and $m$ divides $n$, to construct two classes of bent…
arXiv:2609.18020v1 Announce Type: cross Abstract: A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection…
arXiv:2609.18802v1 Announce Type: new Abstract: We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from…
arXiv:2609.18166v1 Announce Type: new Abstract: We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than…
arXiv:2609.18707v1 Announce Type: new Abstract: Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable. We give an FPRAS for TV distance…
arXiv:2608.12946v3 Announce Type: replace-cross Abstract: We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using…
Showing 1 day · 57 items available
