Sun, Jul 23, 2017

# Sums of geometric series

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for $$n$$ hyperplanes in $$d$$ dimensions only need space proportional to $$n^d$$.

$\sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1).$

Sat, Jul 22, 2017

# Infinite Number of Primes

The erroneous proof I hear most often is: Suppose $$P$$ is a finite set that contains all the primes, then $$p^* = 1 + \prod_{p \in P} p$$ is prime. Indeed, the flaw is that $$p^*$$ is not necessarily prime but rather must be a multiple of some prime not in $$P$$.

Fri, Jul 21, 2017

# Quantum Computer Algorithms

Sat, Apr 22, 2017

# Recurrences

## Theorem

Let $$a \in \mathbb{N}$$, $$t < a \in \mathbb{N}$$, and $$b \in \mathbb{R}$$. Defining $$A_t$$ to be some real number and

$A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N},$

then

$A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}.$

Fri, Apr 21, 2017

# Converging series

Let $$-1 < x < 1$$,

$1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}.$

Wed, May 4, 2016

# Polynomial-time approximation schemes

## PTAS

$$(1\pm\varepsilon)$$-approximation with complexity $$O(n^{f(\varepsilon)})$$.

Wed, Apr 27, 2016

# Equivalence of 3SUM problems

???

## Reducing 3SUMx3 to 3SUMx1

$(a, 3), (b, 4), (c, -7)$

Thu, Apr 14, 2016

# Log Log Log

## Theorem

$\frac{\log n}{\log \log n}! = \Theta(n)$

Tue, Apr 12, 2016

# 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$$ if $$N \cap S \neq \emptyset$$ for all $$S \in \mathcal{F}$$ with $$\mu(S) \ge \varepsilon$$.

Sun, Jan 17, 2016

# $$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 to fix which point of a $$q$$-cell we want to include in the hypercube, it suffices to add the $$n$$ hyperplanes of equation $$x_i = 0$$ to the arrangement. With those additional hyperplanes, the arrangement is such that each $$q$$-cell of the arrangement with $$q > 0$$ contains a $$0$$-cell of the arrangement, hence, we only need the hypercube to intersect, for each $$0$$-cell $$\nu$$ of the arrangement, an hypersphere of center $$\nu$$ and arbitrarily small radius. The inequalities of the polyhedral set defining our hypercube will thus only depend on the position of the $$0$$-cells of our arrangement.