TILens turns technical updates into a focused daily brief: official releases,
trusted reporting, and practitioner analysis, deduplicated and organized by topic.
arXiv:2609.29586v1 Announce Type: cross Abstract: Step recursion is a form of bounded recursion in which each recursive call moves from an input y to a prescribed predecessor $\rho_g(y)$. Its depth $D_g(y)$ is the exact…
arXiv:2609.29145v1 Announce Type: cross Abstract: A generative search answer can cite a supported passage yet omit a source relationship that changes its interpretation. We specify a claim-gated audit of the…
arXiv:2609.30042v1 Announce Type: cross Abstract: We study the computational complexity of peak-oriented rationalizability, a survey based revealed-preference test introduced by Seror (2026). We provide a…
arXiv:2609.30139v1 Announce Type: new Abstract: A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general…
arXiv:2510.16420v3 Announce Type: replace-cross Abstract: As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical…
arXiv:2609.29497v1 Announce Type: cross Abstract: Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a…
arXiv:2609.28691v1 Announce Type: new Abstract: A communication problem can have far more possible inputs than its communication cost would suggest. Must its difficulty already be present on a much smaller set of…
arXiv:2609.28839v1 Announce Type: new Abstract: We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over…
arXiv:2603.26561v3 Announce Type: replace-cross Abstract: The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer…
arXiv:2609.29568v1 Announce Type: new Abstract: We prove an $n^2\log\log n$ lower bound for rational arithmetic circuits computing the permanent over characteristic zero. Additions and scalar operations are free, while…
arXiv:2609.29585v1 Announce Type: new Abstract: Step recursion allows recursive computation to move through a canonical hierarchy in jumps, or strides. Suppose a function algebra is allowed to use several primitive…
arXiv:2609.30019v1 Announce Type: cross Abstract: We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield…
arXiv:2609.29120v1 Announce Type: new Abstract: For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the…
arXiv:2609.29302v1 Announce Type: new Abstract: Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $\Omega(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above…
arXiv:2608.16150v2 Announce Type: replace 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…
arXiv:2609.30105v1 Announce Type: cross Abstract: For an arbitrary isotropic log-concave distribution $P$ on $\mathbb{R}^d$, we prove that the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a…
arXiv:2609.30064v1 Announce Type: cross Abstract: It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $\Theta(\sqrt{n})$. More precisely, it is tightly concentrated in the interval…
arXiv:2507.07942v3 Announce Type: replace Abstract: In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of…
arXiv:2609.28751v1 Announce Type: cross Abstract: We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize…
arXiv:2609.30203v1 Announce Type: cross Abstract: We continue the study initiated by Parnas and Shraibman~\cite{PARNAS2026264} who gave upper bounds on the binary rank of $0,1$ matrices which have a small rank over the…