A sentence like $$ \forall a \in A : P(a) $$ is said to be Vacuously true if $A$ is the empty set, no matter what the predicate $P$ was. For example the sentence $$ \forall x \in \mathbb{R}$$ such that $$x^2 < 0 : x = 23 $$ is true (vacuously).
This could be tricky in some cases. An example I found in the exercises of the book Topology 2nd Ed. by Munkres (which is an awesome book btw), showed this sentence and asked if is true or not, if the two sets $A,B$ are guaranteed to be non-empty or not: $$ (A \times B) \subseteq ( C\times D) \implies A \subseteq C \mbox{ and } B \subseteq D $$.
After some time brushing the rust off my brain, this statement turned out to be true (as the intuition would expect) only if $A$ and $B$ are non-empty. Quiet a surprising result. A counter example case occurs when $A$ is empty but $B$ isn't, in which case $ A\times B$ is empty, in which case the statement holds vacuously although $B$ might not be a subset of $D$.
"Beneath this mask there is more than flesh. Beneath this mask there is an idea, Mr. Creedy, and ideas are bulletproof" - V for Vendetta
Showing posts with label Math. Show all posts
Showing posts with label Math. Show all posts
Tuesday, February 22, 2011
Thursday, March 4, 2010
The power of coding
The problem:
You have a bit vector $\langle a,b \rangle$, and I have another bit vector $\langle c,d \rangle$. We want to compute the scalar product of the two. Typically, we would need at least two multiplications and one addition ($\ell$ multiplications and $\ell-1$ additions for bit vectors of length $\ell$).
Using a certain algebraic property of some algebraic objects, we can do it using two additions and one multiplication ($2(\ell-1)$ additions and one multiplication).
We have reduced the number of computations. In cryptography, using homomorphic cryptsystems, multiplications is a big problem. So having reduced that to only one multiplication is big gain. Note also that you just add your vector locally and send me the result, so even less communication overhead.
I have got correctly working examples for vectors up to 6 items till now. I am working on increasing that number and getting to know the upper limit or any other limitations. So far it works for vectors over $\mathbb{R}$ not just bit vectors.
You have a bit vector $\langle a,b \rangle$, and I have another bit vector $\langle c,d \rangle$. We want to compute the scalar product of the two. Typically, we would need at least two multiplications and one addition ($\ell$ multiplications and $\ell-1$ additions for bit vectors of length $\ell$).
Using a certain algebraic property of some algebraic objects, we can do it using two additions and one multiplication ($2(\ell-1)$ additions and one multiplication).
We have reduced the number of computations. In cryptography, using homomorphic cryptsystems, multiplications is a big problem. So having reduced that to only one multiplication is big gain. Note also that you just add your vector locally and send me the result, so even less communication overhead.
I have got correctly working examples for vectors up to 6 items till now. I am working on increasing that number and getting to know the upper limit or any other limitations. So far it works for vectors over $\mathbb{R}$ not just bit vectors.
Subscribe to:
Posts (Atom)