A polynomial-time $n^{1-\varepsilon}$-approximation of Max-Clique is a single deterministic polynomial-time algorithm returning an integer $a(G)$ such that $a(G)\leq\omega(G)\leq n^{1-\varepsilon}a(G)$ on every nonempty $n$-vertex graph. The algorithm estimates the optimum; it is not required to return a clique. This is the convention in the introduction of Håstad's paper.

The input uses the binary graph encoding and the output uses mathlib's binary encoding of natural numbers. Polynomial time is certified by a fixed finite stack machine. The exponent $\varepsilon$ is fixed before choosing the algorithm.