Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
36 articles · 3 sources · 36 papers ·
Top topics: Algorithms · AI
arXiv:2609.04160v1 Announce Type: cross Abstract: Exact CNOT synthesis asks for a minimum-size CNOT circuit implementing an invertible linear transformation. Although several related synthesis models have been shown to…
arXiv:2609.04046v1 Announce Type: new Abstract: What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer…
arXiv:2603.15565v2 Announce Type: replace Abstract: Let $R_1 := \begin{pmatrix}1&1\\1&0\end{pmatrix}$, and write $R_n := R_1^{\otimes n}$ for the $N \times N$ disjointness matrix, where $N = 2^n$. We construct new…
arXiv:2609.03469v1 Announce Type: new Abstract: We study the computational complexity of solving promise systems of equations over finite algebras. Given two algebras $\mathbf{A}$ and $\mathbf{B}$ with a homomorphism…
arXiv:2609.03508v1 Announce Type: cross Abstract: The Semidefinite Programming (SDP) relaxation of the Maximum Cut (Max-Cut) problem is exact when its optimal value equals the integer maximum cut, geometrically…
arXiv:2609.03065v1 Announce Type: cross Abstract: Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it…
arXiv:2609.03628v1 Announce Type: new Abstract: We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let…
arXiv:2609.02180v2 Announce Type: replace-cross Abstract: Let $0 < \alpha \leq 1/2$. We say that a finite point set $P$ in $\mathbb{R}^d$ is $\alpha$-split by a hyperplane $h$ if each of the closed half-spaces…
arXiv:2608.09368v2 Announce Type: replace-cross Abstract: A target moves between two sites according to a discrete-time Markov chain with a $2\times2$ transition matrix $M$. At each epoch one site is searched at…
arXiv:2507.21758v4 Announce Type: replace-cross Abstract: Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve…
arXiv:2604.16735v2 Announce Type: replace Abstract: In this paper, we investigate the relationships between the volumes of four convex bodies: the cut polytope, metric polytope, rooted metric polytope, and elliptope,…
arXiv:2407.19608v2 Announce Type: replace-cross Abstract: The \emph{Stanley--Yan} (SY) \emph{inequality} gives the ultra-log-concavity for the numbers of bases of a matroid which have given sizes of intersections with…
arXiv:2609.04122v1 Announce Type: cross Abstract: Synchronization strings attach deterministic position labels to a stream that survive insertions and deletions. Haeupler and Shahrasbi introduced these objects, and…
arXiv:2609.03682v1 Announce Type: new Abstract: This paper studies the problem of fair division of indivisible goods among $k$ groups of $n_1,\ldots, n_k$ agents. We look at the worst downward deviation…
arXiv:2509.22849v3 Announce Type: replace-cross Abstract: Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the…
arXiv:2608.12678v2 Announce Type: replace-cross Abstract: Let $P$ be a finite nonempty poset with $n$ elements, let $f:P\to\{1,\ldots,n\}$ be a uniformly random order-preserving bijection, and put…
arXiv:2609.03896v1 Announce Type: cross Abstract: The way numbers are represented strongly influences which arithmetic structures are easy to see. The \emph{prime clockwork} is a recursively growing discrete dynamical…
arXiv:2609.04161v1 Announce Type: new Abstract: We study the job shop scheduling problem with a conflict graph (JSC), in which adjacent jobs in the conflict graph cannot be processed simultaneously on different…
arXiv:2608.15398v2 Announce Type: replace-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…
arXiv:2411.08685v2 Announce Type: replace-cross Abstract: Consider a graph $G$ with a path $P$ of order $n$. What conditions force $G$ to also have a long induced path? As complete bipartite graphs have long paths but…
Showing 1 day · 36 items available
