What is a good reference for NP hardness in the machine learning/optimization/operations research context? I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:

Theorem 1.1. For any constant ϵ &gt; 0, it is NP-hard to find a
halfspace that correctly labels (1/2 + ϵ)-fraction of given examples
over {0, 1} n even when there exists a monomial that agrees with a (1
− ϵ)-fraction of the examples.
https://people.eecs.berkeley.edu/~prasad/Files/mono.pdf

At this point, the definition of NP-hard is not even defined. I have seen many examples like this, which makes me wonder
&quot;Do all these  thousands of authors have the same definition of NP-hard/complexity notions&quot;?
&quot;These contexts seem so different from the usual contexts where NP-hardness come up such as graph coloring or traveling salesman problem, how can I be sure that these notions of complexity/NP hardness are equivalent?&quot;
Can someone point out a good reference for studying complexity theory in a machine learning/operation research/optimization context? Many thanks!
In modern papers, and unless stated otherwise, NP-hardness is one of the following:

A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha &lt; 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.
Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.