
Polynomialtime approximation schemes
PTAS \((1\pm\varepsilon)\)approximation with complexity \(O(n^{f(\varepsilon)})\). EPTAS \((1\pm\varepsilon)\)approximation with complexity \(O(f(\varepsilon) n^c)\). FPTAS \((1\pm\varepsilon)\)approximation with complexity \(O(poly(\frac{1}{\varepsilon}) n^c)\). \[ \text{FPTAS} \subseteq \text{FPT} \]

Equivalence of 3SUM problems
Reducing 3SUMx1 to 3SUMx3 Let \(T(n)\) be the complexity of solving 3SUMx1(S) using the following algorithm: split the input \(S = \{\,x_1 , x_2 , \ldots , x_n\,\}\) in three disjoint sets \(A\), \(B\) and \(C\) of equal size. if \(x_i + x_j + x_k = 0 , i <...

Smallish
\[ \begin{align} K^2! &= \sqrt{\frac{\log n}{\log \log n}}^2!\ &= \frac{\log n}{\log \log n}!\ \lim_{K^2 \to \infty} K^2! &= \sqrt{2\pi \frac{\log n}{\log \log n}} \left( \frac{\frac{\log n}{\log \log n}}{e}\right)^\frac{\log n}{\log \log n}\ \lim_{n \to \infty} K^2! &= \sqrt{2\pi \frac{\log n}{\log \log n}} \left( \frac{\frac{\log n}{\log \log n}}{e}\right)^\frac{\log n}{\log \log n}\ &=...

VCdimension
Definition 1 (Espilon net) Let \(X\) be a set, let \(\mu\) be a probability measure on \(X\), let \(\mathcal{F}\) be a system of \(\mu\)measurable subsets of \(X\), and let \(\varepsilon \in [0,1]\) be a real number. A subset \(N\subseteq X\) is called an \(\varepsilon\)net for \((X,\mathcal{F})\) with respect to \(\mu\)...

\(d\) hyperplanes intersection bounds
We bound the position of the \(0\)cells of an arrangement of hyperplanes in \(\mathbb{R}^d\). This allows, for example, to build an hypercube that intersects all cells of the arrangement. Such an hypercube must contain at least one point of each cell of the arrangement. When \(q > 0\), in order...

Polyhedral sets
A polyhedral set set in \(\mathbb{R}^d\) is the intersection of a finite number of closed halfspaces, and a (convex) polytope is a bounded polyhedral set. This definition of a polytope is called a halfspace representation (Hrepresentation or Hdescription). A defining halfspace of a polyhedral set \(P\) is a facetdefining halfspace...

Symbols
\[ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C} \] \(\mathbb{N}\) is the set of natural numbers. \(\mathbb{Z}\) is the set of integers. \(\mathbb{Z}\) stands for Zahlen, the plural of the german word Zahl. \(\mathbb{Q}\) is the set of rational numbers. \(\mathbb{Q}\) stands for quoziente, the italian word for...

Probabilistic primality testing
Sage implementation