• Polynomial-time 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}\ &=...

  • VC-dimension

    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 (H-representation or H-description). A defining halfspace of a polyhedral set \(P\) is a facet-defining 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