Jul 2026· Foundations of Computational Mathematics· 0 citations· 44 references
TL;DR
Approximation to a solution of a computational problem for -approximation to a solution of a computational problem for -approximation to a solution of a computational problem for -approximation to a solution of a computational problem.
Abstract
<jats:p>
Generalised hardness of approximation (GHA) is the phenomenon that one can easily compute an
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\epsilon $$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mi>ϵ</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
-approximation to a solution of a computational problem for
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\epsilon> \epsilon _1 > 0$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>ϵ</mml:mi>
<mml:mo>></mml:mo>
<mml:msub>
<mml:mi>ϵ</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mo>></mml:mo>
<mml:mn>0</mml:mn>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, but for
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\epsilon < \epsilon _1$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>ϵ</mml:mi>
<mml:mo><</mml:mo>
<mml:msub>
<mml:mi>ϵ</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
(the approximation threshold) it suddenly becomes hard, for example, non-computable or intractable (non-polynomial time). In this paper we demonstrate the phenomenon that GHA happens when using AI techniques for solving inverse problems, namely training neural networks (NNs) to optimally perform on the training data. In particular, for any non-zero underdetermined linear inverse problem the following phase transition can occur: For a certain family of training sets
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\Omega $$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mi>Ω</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, one can prove the existence of optimal NNs for solving the inverse problem for each
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathcal {T}\in \Omega $$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>T</mml:mi>
<mml:mo>∈</mml:mo>
<mml:mi>Ω</mml:mi>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, however, these optimal neural networks can only be computed to a certain accuracy
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\epsilon _1 > 0$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:msub>
<mml:mi>ϵ</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mo>></mml:mo>
<mml:mn>0</mml:mn>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
. Below the approximation threshold
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\epsilon _1$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msub>
<mml:mi>ϵ</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, not only does it become intractable to compute the NNs, it becomes impossible regardless of computing power, and no randomised algorithm can solve the problem with probability better than 1/2. Moreover, despite the existence of a stable optimal NN, any attempts of computing it below two times the approximation threshold
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$2\epsilon _1$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mn>2</mml:mn>
<mml:msub>
<mml:mi>ϵ</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
will yield an unstable NN. Our results use and extend the current mathematical framework of the Solvability Complexity Index (SCI) hierarchy and initiate a program for analysing the GHA phenomenon throughout computational mathematics and AI. GHA generalises the phenomenon of hardness of approximation in discrete computations to arbitrary computational problems.
</jats:p>
<jats:p>
Seymour’s second neighborhood conjecture states that every oriented graph
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\vec {G}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mover>
<mml:mi>G</mml:mi>
<mml:mo>→</mml:mo>
</mml:mover>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
has a Seymour vertex, namely,
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\vec {G}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mover>
<mml:mi>G</mml:mi>
<mml:mo>→</mml:mo>
</mml:mover>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
has a vertex whose second-order out-neighborhood is at least as large as its first-order out-neighborhood. In this paper, we approach the conjecture by considering an inhomogeneous random graph
<jats:italic>G</jats:italic>
, where each edge
<jats:italic>e</jats:italic>
in the complete graph
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$K_n$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msub>
<mml:mi>K</mml:mi>
<mml:mi>n</mml:mi>
</mml:msub>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
appears independently with probability
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$p_n(e)$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:msub>
<mml:mi>p</mml:mi>
<mml:mi>n</mml:mi>
</mml:msub>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>e</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
. Under suitable density and regularity conditions, we show that every orientation of
<jats:italic>G</jats:italic>
contains a Seymour vertex with high probability, confirming the conjecture asymptotically. Moreover, if we consider an inhomogeneous random oriented graph
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\vec {G}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mover>
<mml:mi>G</mml:mi>
<mml:mo>→</mml:mo>
</mml:mover>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
by assigning an orientation to each edge of
<jats:italic>G</jats:italic>
independently with equal probability, we prove that
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\vec {G}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mover>
<mml:mi>G</mml:mi>
<mml:mo>→</mml:mo>
</mml:mover>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
contains a Seymour vertex with high probability across a broader range of regimes.
</jats:p>
Y. Shang· Periodica Mathematica Hungar...· 0 citations
<jats:p>
Lexicographical extensions of well-known separation theorems for convex sets in
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msup>
<mml:mrow>
<mml:mi>R</mml:mi>
</mml:mrow>
<mml:mi>n</mml:mi>
</mml:msup>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
are provided in the literature. Particularly, recent theorems regarding open and closed separation of a convex set from any outside point by linear operators from
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathbb {R}^n$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msup>
<mml:mrow>
<mml:mi>R</mml:mi>
</mml:mrow>
<mml:mi>n</mml:mi>
</mml:msup>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
to
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msup>
<mml:mrow>
<mml:mi>R</mml:mi>
</mml:mrow>
<mml:mi>m</mml:mi>
</mml:msup>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, in the sense of the lexicographical order of
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathbb {R}^m$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:msup>
<mml:mrow>
<mml:mi>R</mml:mi>
</mml:mrow>
<mml:mi>m</mml:mi>
</mml:msup>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, for each
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$m\in \{1,\ldots ,n\}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>m</mml:mi>
<mml:mo>∈</mml:mo>
<mml:mo>{</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>,</mml:mo>
<mml:mo>…</mml:mo>
<mml:mo>,</mml:mo>
<mml:mi>n</mml:mi>
<mml:mo>}</mml:mo>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, allow to define two new families of properties for convex sets. Based on these results, that we review and extend in this paper, we provide dual characterizations for the consistency of two kinds of systems defined by weak and/or strict lexicographical linear inequalities, and for those inequalities which are satisfied for every solution of a given system. Such results are formulated in terms of appropriate convex hulls of certain sets depending on the coefficients of the system.
</jats:p>
J. Vicente-Pérez, Margarita M. L. Rodríguez· TOP - An Official Journal of...· 0 citations
<jats:p>
In this paper, we introduce the notion of generalized
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathcal {W}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mi>W</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
-Gorenstein modules respect to some subclass
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathcal {W}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mi>W</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, extending the classical notion of Gorenstein projective modules. By exploiting the correspondence between projective modules over the endomorphism ring
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\textrm{End}_R(C)$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:msub>
<mml:mtext>End</mml:mtext>
<mml:mi>R</mml:mi>
</mml:msub>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>C</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
of a module
<jats:italic>C</jats:italic>
and elements of its additive closure
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathcal {W}=\textrm{Add}_R(C)$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:mi>W</mml:mi>
<mml:mo>=</mml:mo>
<mml:msub>
<mml:mtext>Add</mml:mtext>
<mml:mi>R</mml:mi>
</mml:msub>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>C</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, we establish a fundamental correspondence between Gorenstein projective
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\textrm{End}_R(C)$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:msub>
<mml:mtext>End</mml:mtext>
<mml:mi>R</mml:mi>
</mml:msub>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>C</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
-modules and generalized
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\textrm{Add}_R(C)$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mrow>
<mml:msub>
<mml:mtext>Add</mml:mtext>
<mml:mi>R</mml:mi>
</mml:msub>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>C</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
-Gorenstein modules. This result refines existing relative homological settings and provides a natural extension of well-known results in Gorenstein homological algebra. We explore key properties, such as closure under direct summands and sums, and identify conditions under which the class of generalized
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>$$\mathcal {W}$$</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">
<mml:mi>W</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
-Gorenstein modules coincides with other classes of modules, like Gorenstein projective modules.
</jats:p>
Driss Bennis, C. Lomp, Abderrazak Nassir· Algebras and Representation...· 0 citations
<jats:p>
The thermal partition function,
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>Z</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mi>Z</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
, of a
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>CFT_d</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:mi>C</mml:mi>
<mml:mi>F</mml:mi>
<mml:msub>
<mml:mi>T</mml:mi>
<mml:mi>d</mml:mi>
</mml:msub>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
on
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>S^{d-1}</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:msup>
<mml:mi>S</mml:mi>
<mml:mrow>
<mml:mi>d</mml:mi>
<mml:mo>−</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
</mml:msup>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
is parameterized by the inverse temperature
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\beta</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mi>β</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
along with
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\lfloor d/2\rfloor</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:mo stretchy="false" form="prefix">⌊</mml:mo>
<mml:mi>d</mml:mi>
<mml:mi>/</mml:mi>
<mml:mn>2</mml:mn>
<mml:mo stretchy="false" form="postfix">⌋</mml:mo>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
angular velocities
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\omega_i</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:msub>
<mml:mi>ω</mml:mi>
<mml:mi>i</mml:mi>
</mml:msub>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
. In this paper, we investigate the behaviour of this partition function when
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>n</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mi>n</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
of the
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\omega_i</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:msub>
<mml:mi>ω</mml:mi>
<mml:mi>i</mml:mi>
</mml:msub>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
are scaled to unity (the largest allowed value) at fixed values of the other
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>(\lfloor d/2\rfloor-n)</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:mo stretchy="false" form="prefix">(</mml:mo>
<mml:mo stretchy="false" form="prefix">⌊</mml:mo>
<mml:mi>d</mml:mi>
<mml:mi>/</mml:mi>
<mml:mn>2</mml:mn>
<mml:mo stretchy="false" form="postfix">⌋</mml:mo>
<mml:mo>−</mml:mo>
<mml:mi>n</mml:mi>
<mml:mo stretchy="false" form="postfix">)</mml:mo>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
angular velocities. We argue that
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\ln Z</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:mrow>
<mml:mi mathvariant="normal">ln</mml:mi>
<mml:mo></mml:mo>
</mml:mrow>
<mml:mi>Z</mml:mi>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
develops a simple pole in
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>(1-\omega_i)</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:mo stretchy="false" form="prefix">(</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>−</mml:mo>
<mml:msub>
<mml:mi>ω</mml:mi>
<mml:mi>i</mml:mi>
</mml:msub>
<mml:mo stretchy="false" form="postfix">)</mml:mo>
</mml:mrow>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
for each
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\omega_i</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:msub>
<mml:mi>ω</mml:mi>
<mml:mi>i</mml:mi>
</mml:msub>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
that is scaled to unity. The residue of this product of poles is a theory-dependent (so non-universal) function of
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>\beta</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mi>β</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
and the fixed angular velocities. The inverse Laplace transformation of this partition function constrains the functional form of the field theory entropy as a function of charges in a limit in which angular momenta and the twist are scaled as follows. While
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>n</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mi>n</mml:mi>
</mml:math>
</jats:alternatives>
</jats:inline-formula>
special angular momenta
<jats:inline-formula>
<jats:alternatives>
<jats:tex-math>J_1\ldots J_n</jats:tex-math>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mml:mrow>
<mml:msub>
<mml:mi>J</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mi>…</mml:mi>
H. Anand, N. Benjamin, Vipul Kumar et al.· SciPost Physics· 8 citations· ⚡3
