Sun, Jul 23, 2017

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). \]

Read more about Sums of geometric seriesSat, Jul 22, 2017

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\).

Read more about Infinite Number of PrimesFri, Jul 21, 2017

Notes from June 2015 containing the following: Phase kick-back, Deutsch's algorithm, Fourier sampling, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Preimage of a function, Simon's algorithm, Grover's algorithm, Amplitude amplification, Quantum Fourier Transform, and Shor's algorithm.

Read more about Quantum Computer AlgorithmsSat, Apr 22, 2017

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}. \]

Read more about RecurrencesFri, Apr 21, 2017

Let \(-1 < x < 1\),

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

Read more about Converging seriesWed, May 4, 2016

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

Read more about Polynomial-time approximation schemesWed, Apr 27, 2016

???

\[ (a, 3), (b, 4), (c, -7) \]

Read more about Equivalence of 3SUM problemsThu, Apr 14, 2016

Tue, Apr 12, 2016

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\).

Read more about VC-dimensionSun, Jan 17, 2016

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.

Read more about \(d\) hyperplanes intersection bounds