Skip to content
TILens What matters today in tech v0.3.2
Theme

Daily edition · Algorithms

The daily ledger

TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.

22 Sep 2026 edition

76 articles · 3 sources · 76 papers ·

Top topics: Algorithms · AI

Algorithms

Lee-Yang theorem for fermions

arXiv:2609.23942v1 Announce Type: cross Abstract: Lee-Yang theorems are a powerful tool for studying many-body systems, with applications ranging from analyzing phase transitions to proving the efficiency of certain…

Source: arXiv cs.CC Chaithanya Rayudu, Takahiro Misawa, Andrew Zhao, Jun Takahashi
Algorithms

Complexity of Output Feedback Stabilization

arXiv:2609.20636v2 Announce Type: replace-cross Abstract: We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical…

Source: arXiv cs.CC Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang
Algorithms

Interval number for tournaments in P3-convexity

arXiv:2609.22640v1 Announce Type: new Abstract: We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by…

Source: arXiv cs.CC Idian C. Capozzoli, Yan S. Couto, Enrique Junchaya
Algorithms

Undefinability of Approximation of 2-to-2 Games

arXiv:2504.03523v3 Announce Type: replace-cross Abstract: Recent work by Atserias and Dawar (J. Log. Comp 2019) and Tucker-Foltz (LMCS 2024) has established undefinability results in fixed-point logic with counting…

Source: arXiv cs.CC Anuj Dawar, B\'alint Moln\'ar
Algorithms

SC Derandomization for Regular ROBPs and Models Beyond BPL

arXiv:2609.23603v1 Announce Type: new Abstract: We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple…

Source: arXiv cs.CC Kuan Cheng, Ruiyang Wu
Algorithms

Bit-counting complexity classes

arXiv:2606.04406v3 Announce Type: replace Abstract: We define bit-counting complexity classes whose membership depends on the binary profile of the number of accepting paths of non-deterministic polynomial time Turing…

Source: arXiv cs.CC Tayfun Pay
Algorithms

Strong NP-Completeness of Unrestricted Balanced Mobiles

arXiv:2609.24654v1 Announce Type: new Abstract: A mobile is a rooted full binary tree whose leaves carry positive integer weights. The imbalance of an internal node is the absolute difference between the total weights…

Source: arXiv cs.CC Andrei Popa, Alexandru Popa
Algorithms

Sumset Structure in Local Computation

arXiv:2609.22732v1 Announce Type: new Abstract: We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each…

Source: arXiv cs.CC Alexander Golovnev, Mohit Gurumukhani
Algorithms

Hierarchies within TFNP: building blocks and collapses

arXiv:2507.21550v3 Announce Type: replace Abstract: In all well-studied $\mathsf{TFNP}$ subclasses (e.g. $\mathsf{PPP}$ etc.), the canonical complete problem takes as input a polynomial-size circuit $C$ whose…

Source: arXiv cs.CC Surendra Ghentiyala, Zeyong Li
Algorithms

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

arXiv:2609.24593v1 Announce Type: cross Abstract: We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over…

Source: arXiv cs.CC Hans Raj Tiwary, Michel Grabisch
Algorithms

Unrestrictions and concise secant varieties

arXiv:2604.24879v3 Announce Type: replace-cross Abstract: We introduce the concise secant varieties, which are, informally speaking, modular partial desingularisations of secant varieties to Segre embeddings. More…

Source: arXiv cs.CC Jakub Jagie{\l}{\l}a, Joachim Jelisiejew
Algorithms

Formalizing PARITY Circuit Lower Bounds in Lean

arXiv:2609.24188v1 Announce Type: new Abstract: We formalize Hastad's PARITY lower bound in Lean using the switching lemma. For every fixed d >= 2, formulas and DAG circuits of computation depth at most d computing…

Source: arXiv cs.CC Saint Wesonga
Algorithms

Many Proof Complexity Generators Inside One Demi-Bits Generator

arXiv:2609.23228v1 Announce Type: new Abstract: For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator*…

Source: arXiv cs.CC Xin Li, Hanlin Ren, Yan Zhong
Algorithms

Finding a Positive Index Nash Equilibrium is PPADS-Complete

arXiv:2609.23879v1 Announce Type: new Abstract: Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove…

Source: arXiv cs.CC Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan
Algorithms

Three Hardness Results for Graph Similarity Problems

arXiv:2309.03810v3 Announce Type: replace Abstract: Notions of graph similarity provide alternative perspective on the graph isomorphism problem and vice-versa. In this paper, we consider measures of similarity arising…

Source: arXiv cs.DM He Sun, Danny Vagnozzi

Showing 1 day · 76 items available