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…
Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
76 articles · 3 sources · 76 papers ·
Top topics: Algorithms · AI
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…
arXiv:2609.21785v2 Announce Type: replace-cross Abstract: The satisfiability problem for word equations asks whether variables can be replaced by words so that the two sides become equal. For regular word equations, in…
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…
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…
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…
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…
arXiv:2609.24272v1 Announce Type: new Abstract: We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and…
arXiv:2609.23015v1 Announce Type: new Abstract: Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over…
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…
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…
arXiv:2609.22669v1 Announce Type: cross Abstract: We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our…
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…
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…
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…
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…
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…
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*…
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…
arXiv:2511.02983v2 Announce Type: replace-cross Abstract: We study geometric characterizations of unbounded integer polynomial optimization problems. Unboundedness along a ray characterizes unbounded integer linear and…
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…
Showing 1 day · 76 items available