An elementary proof of the Koml\'os conjecture
arXiv:2609.20979v2 Announce Type: replace-cross Abstract: We give an elementary proof of the Koml\'os conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors…
Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
56 articles · 3 sources · 56 papers ·
Top topics: Algorithms · AI
arXiv:2609.20979v2 Announce Type: replace-cross Abstract: We give an elementary proof of the Koml\'os conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors…
arXiv:2604.01519v3 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:2608.18839v3 Announce Type: replace-cross Abstract: We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or…
arXiv:2609.27951v1 Announce Type: cross Abstract: We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in…
arXiv:2609.21567v2 Announce Type: replace-cross Abstract: Quantum Signal Processing is a powerful quantum framework for generating and approximating univariate polynomials. However, QSP is often limited by circuit-depth…
arXiv:2609.27129v1 Announce Type: cross Abstract: We prove quantum soundness of the total-degree diagonal line-vs-point test using the individual-degree soundness theorem of Ji, Natarajan, Vidick, Wright, and Yuen. A…
arXiv:2606.28639v3 Announce Type: replace-cross Abstract: We establish mathematical limits of algorithmic safety verification for Turing-complete self-modifying systems, the class in which recursive self-improvement…
arXiv:2609.28308v1 Announce Type: cross Abstract: Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which…
arXiv:2609.28028v1 Announce Type: cross Abstract: For every fixed integers $r \ge 4$ and $2 \le k \le r-2$, we construct $r$-dimensional cubical sheaf complexes whose degree-$k$ CSS codes have positive constant rate,…
arXiv:2608.04243v1 Announce Type: cross Abstract: Multi-head attention layers produce vector representations that support multiple downstream tasks. We establish bounds on the number of heads required in two simple and…
arXiv:2609.28243v1 Announce Type: new Abstract: The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f from…
arXiv:2609.28207v1 Announce Type: new Abstract: In symbolic dynamics, the fixed-point construction from arXiv:0910.2415 defines shift spaces of finite type whose configurations embed infinite hierarchies of tilings.…
arXiv:2607.18334v2 Announce Type: replace-cross Abstract: For the circulant graph $C_n(1,2)$ with $n\ge10$ even, the $\F_2$ system requiring every quadrilateral to be unbalanced is consistent and its solutions form…
arXiv:2609.27495v1 Announce Type: cross Abstract: We prove that the Tur\'an density of the tetrahedron $K_4^{(3)}$ satisfies $\pi(K_4^{(3)}) \le 312372062889819/560000000000000 < 0.557808$, improving Baber's upper bound…
arXiv:2609.28451v1 Announce Type: cross Abstract: We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to…
arXiv:2609.27583v1 Announce Type: cross Abstract: A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly…
arXiv:2609.28023v1 Announce Type: cross Abstract: The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1, \ldots, w_{|V(G)|} \in \Sigma$ and a decoder $D \subseteq \Sigma^2$ for…
arXiv:2609.27168v1 Announce Type: cross Abstract: A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such…
arXiv:2609.27483v1 Announce Type: cross Abstract: We give snakes that are longer than the previous best known in dimensions 13 through 20 and improve the general lower bound for every dimension $d \geq 21$. Our explicit…
arXiv:2609.26851v1 Announce Type: new Abstract: We study representations for relation algebras corresponding to certain edge colourings of complete graphs. Previously suitable colourings were obtained for the number of…
Showing 1 day · 56 items available