CS Paper Radar

Generic Local Identifiability Does Not Imply Generic Global Identifiability in Linear Networks

Anders Hansson

eess.SY math.OC ·submitted 2026-10-13 11:56 UTC · v1

Abstract

We give a counterexample to the implication from generic local to generic global identifiability for linear networks with a fixed topology, independently unknown edge coefficients, and selected excited and measured nodes. A six-node network with nine unknown coefficients has exactly two compatible parameter vectors generically. Adding six excited and measured nodes preserves this ambiguity while making the added coefficients directly recoverable. The resulting twelve-node structure has forty-two independent unknown coefficients and zero diagonal. For every positive bound on the largest eigenvalue magnitude, a nonempty open set of parameters has two distinct compatible networks satisfying that bound. This holds for both real and complex coefficients. Other open regions have exactly one admissible solution. The proof uses a rational transformation exchanging the two solutions and a common limiting matrix whose fourth power vanishes. Exact rational-number certificates verify an explicit pair. The construction also extends algebraically when the unknown coordinates are whole rational transfer functions. Genericity in prescribed numerator and denominator coefficient families, and the requirement that every transfer function vanish at infinite frequency, remain separate questions.

Closest papers

Nearest neighbours by meaning across the whole index.

Polynomial Residual Networks are Generically Identifiable

cs.LG math.AG ·2026-10-24 ·Isabel Dahlgren, Giovanni Luca Marchetti, Kathlén Kohn
theory similarity 0.59
Abstract

We prove identifiability results for constant-width residual networks with polynomial activations and bias terms. For activations of degree at least five with generic coefficients, the fiber over a generic parameter is a singleton. For activations of degree at least three with no linear term after a suitable translation of the input, the generic fiber is given by translating biases and then scaling weights and translated biases by real roots of unity. These results specialize to networks without bias terms. With the same proof technique, we further derive necessary conditions for critical points of the ResNet parametrization, that are central in singular learning theory.

0.19

Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks

cs.LG math.ACmath.AG ·2026-08-27 ·Kathlén Kohn, Giovanni Luca Marchetti, Alex Massarenti, Massimiliano Mella
theoryhighly cited similarity 0.55
Abstract

Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.

0.43

On the Observability and Controllability of Leaky-ReLU Networks

eess.SY ·2026-08-10 ·Liangjie Sun, Wai-Ki Ching, Shun-ichi Azuma, Tatsuya Akutsu
theory similarity 0.53
Abstract

This paper studies minimum-node observability and controllability of Leaky rectified linear unit (Leaky-ReLU) networks under degree constraints. The objective is to characterize how many state nodes must be measured or directly actuated to determine the initial state from a finite output sequence or to steer the network between arbitrary states within a finite horizon. For observability, a graph-theoretic analysis yields a class-wide upper bound on the minimum number of observation nodes. We construct a family of networks attaining this bound, thereby determining the exact worst-case minimum number of observation nodes. We also construct networks that are observable from a single node over a finite horizon, establishing the exact best-case value of one. By establishing an observability--controllability duality under the corresponding degree constraints, we obtain analogous exact best- and worst-case results for the minimum number of control nodes. A comparison with ReLU networks shows how replacing the zero negative slope with a nonzero slope changes the observation-node requirement. More generally, the observability arguments require only injectivity of the activation function, whereas the controllability results extend to bijective activation functions.

0.04

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

cs.CC ·2026-10-30 ·Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
theory similarity 0.53
Abstract · Made some minor changes

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

0.17

A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees

cs.DC ·2026-08-19 ·Filippo Casagrande, Pierre Fraigniaud, Benjamin Jauregui, Mikaël Rabie
theory similarity 0.53
Abstract · 24 pages, 4 figures

We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally checkable, but solely to the fact that LCL problems are defined only for graphs of maximum degree upper bounded by some arbitrary yet constant value $Δ$. Specifically, we show that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals $[ω(1),o(\log\log^\star n)]$ and $[ω(\log^\star n),o(\log n)]$ whenever these problems are considered in networks with unbounded maximum degrees. This extends the previous results by Schmid (arXiv, 2026), which hold for the polynomial regime only, and by Bousquet, Feuilloley, and Pierron (OPODIS, 2025), which hold for trees only. All our upper bounds are obtained using deterministic algorithms that can be run under the port-numbering model, which is a weak variant of LOCAL, without any a priori information on the number of nodes in the network. Instead, our lower bounds apply to randomized LOCAL, and quantum LOCAL, even if nodes have identifiers in $[1,n]$, and even if they know the exact number of nodes in the network. They even hold under randomized online LOCAL, a strong variant of the LOCAL model. Finally, our lower bounds hold even for trees. Our results are obtained using two main ingredients. The first one is the analysis of a new locally checkable problem called Increasing Degree, parameterized by a function $f:\mathbb{N}\to\mathbb{N}$. Different round complexities can be obtained by tuning the function $f$ accordingly. Our second tool is a general Translation Theorem that enables to transfer results from a given range of complexities to results for a range of lower complexities.

0.16

Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains

cs.DS ·2026-09-29 ·Monaldo Mastrolilli
theory similarity 0.53
Abstract

Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over Boolean polynomial systems. A complete, constructible identity space gives an augmented moment SDP that can be optimized with exact rational feasibility and arbitrary additive accuracy. We give a self-contained geometric implementation: an explicit affine reduction and a simplex of Boolean evaluations supply the radius bounds required by rational ellipsoids. The identity space can be constructed directly or extracted from a supplied graded Groebner basis, including one supplied at a higher truncation degree. An explicit transfer theorem connects this augmented formulation to the original system. Two-sided SoS derivations eliminate the added equality axioms from certificates, with controlled degree and coefficient growth, and imply containment of a projected higher-level moment relaxation in the augmented body. Together with spectral coefficient bounds, this gives polynomial-time search for rational proofs with an additive perturbation. For Min-closed linear systems, propagation constructs the identity space in polynomial time at fixed degree and gives degree-(4t+4) certificates for both signs of each degree-t basis element. Consequently, a rational degree-(8d+4) proof of f + epsilon >= 0 can be found in polynomial time for fixed d whenever f >= 0 has a degree-2d proof. The augmented degree-2d moment SDP can be optimized in polynomial time with exact rational feasibility and a comparison to the original degree-(8d+4) relaxation. Boolean complementation gives the same results for Max-closed systems, including generalized packing and covering. Min-closed systems thus provide a concrete application of the general criteria. All complexity bounds are in the Turing model.

0.43

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng, Juqiu Wang
theory similarity 0.52
Abstract · 98 pages; proof and exposition revised, Lean repository linked

A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

0.24

Approximate clearing in financial networks with credit default swaps: hardness thresholds, a box algorithm, barriers, and exact solvency at bounded degree

cs.CC q-fin.RM ·2026-10-31 ·Michal Čertík
theory similarity 0.51
Abstract · 119 pages including references and complete proof appendices. Scientific code and supporting materials: https://doi.org/10.5281/zenodo.23834…

We study approximate clearing in financial networks with credit default swaps. For weak notions (W) and (I), we prove PPAD-hardness below a threshold approximately $0.2530$ and give a polynomial-time interval algorithm above a threshold approximately $0.2834$. On networks whose CDS writers are solvent ex ante, the corresponding bounds are $(13-\sqrt{153})/4$ and $3-2\sqrt{2}$, approximately $0.1577$ and $0.1716$. The thresholds are sharp for bounded-radius algorithms: for (I) on writer-solvent networks, and for (I) and (W) in general. On non-degenerate networks, (W) and (I) have identical hardness and tractability threshold endpoints. For exact-solvency notion (D), PPAD-hardness holds at every rational error $\varepsilon<1$ on non-degenerate networks. On a restricted unit-notional class, let $d$ be the maximum number of CDS contracts held by a core bank, counted with multiplicity. For rational $\varepsilon\in[1/2,1)$, writing $ρ=(1+\varepsilon)/(1-\varepsilon)$, the problem is polynomial-time solvable when $d<(\lceilρ\rceil+1)ρ$ and PPAD-complete otherwise. At $\varepsilon=1/3$ the boundary is $d=5$ versus $d=6$; below $\varepsilon=1/9$, degree $2$ is already PPAD-complete, while degree $1$ is exactly solvable. These degree results concern (D) and do not close the (W)/(I) approximation windows. We also establish a barrier to Pure-Circuit reductions certified by interval propagation under stated interface and auxiliary-bank restrictions. A finite-precision interval algorithm reduces writer-solvent (I) to point selection in near-stalled boxes; selection is polynomial-time when the residual matrix is symmetric or monotone on each strongly connected component. The general and writer-solvent approximation windows remain open.

0.42