DAtum: September 2005

Delhi Half Marathon Training: Week 1

9/30/2005

Siri Fort: (post tennis session)

Day 1: 5 Km - 21 mins

Day 2: 5 Km - 23 mins

Day 3: 7 Km - 35 mins +

6 eggs + 90 gms whey .

Got to go up to 10 kms next week in 45 mins. Think of Lance. Always think of Lance.

Read more!

Chapter 71

71'st chapter of the Tao Te Ching

Not-knowing is true knowledge.
Presuming to know is a disease.
First realize that you are sick;
then you can move toward health.

There is no spoon.

Inspired by Evelyn Rodriguez's post.

Read more!

Does heapsort make more sense for EDA algorithms ?

9/29/2005

Just a random thought - given that netlist representations of most HDL appear in the form of unbounded trees (parents with greater than 2 children), this can be most easily be represented by list of lists.
Now, if we use a custom memory manager that pre-allocates large chunks, this means that the lists which will be created, be most probably contiguous in memory.. or we can make them contiguous, without loss of great processing power. This in turn means that they are similar to arrays.
Now, heapsort will perform with O(n log(n) ) upper-bounded complexity. But, if the array like structure is enforced, it will be very easy to map it to a similar heap structure (just re-ordering). Which means that heapsort may have better cache-performance than, say quicksort (cos the temporary space required is inside the orginal array heap).
Just a thought.

Read more!

Prediction markets: real life psychohistory?

9/25/2005

This summer, while I was in Tunis, I read a story by Robert Reed called the Opal Ball. It tells of a time with a sort of Ebay-like marketplace, where instead of goods, predictions about the future are traded. It is the norm to put details on potential dates, career strategies, etc. on the market where they are traded like any other futures and it is only quite infrequently that the Market is wrong. The couple in the story tries to go against the market and get married, however it ends up in a bitter divorce. The infant daughter however is kept away from the Market by the father, perhaps in an effort to let chaos run its course.
Perhaps it is because of Heisenberg. A precept of quantum theory says

that which is directly observed as the act of observation changes the nature of that which is observed

This is not a work of fiction.

Friedrich Hayek is considered the father of predictive market theories. He had a strong belief in the fact that price mechanisms carried more information than just its inherent content - which is to say, price. He always maintained this about price mechanisms

that which is the result of human action but not of human design

Language, for instance, carries more information than its content. The pretty little thing at the bard could have said, "I'll call you tomorrow", but its the eyes which tell you if she really will.
This is the basis of the Iowa Electronic Markets. It gained notoriety in accurately predicting the results of the US presidential elections.
How is it different from a poll? A poll is a snapshot of the current distribution of "consumer" preferences. However, in prediction markets, you introduce competition. Therefore, now you analyze the problem with an intent to win. However, you are also part of the problem that needs to be solved.
When designing prediction markets, the risk free rate and required expected return rate is constrained to be zero. The IEM operates two kind of futures (if we consider election outcomes as the market):

Winner-takes-all: contracts pay 0 or 1 dollars depending on whether the candidate won or lost the election

vote-share futures: contracts pay an amount equal to the fraction of vote-share received by the candidate times $1

Intuitively, the vote-share futures can be seen as a distribution of probability of vote-share (think of it this way,for a given contract price - the vote share - the volume indicates his perceived probability of winning). The winner-takes-all futures are actually a subset of the vote-share futures - you are actually pricing the candidate when his vote share is the highest vote-share. The interesting thing in all this is, you actually factor in other people's expectation of votes, while constructing your own. For me, that seems to be an incremental refinement of knowledge.

What makes this abstruse topic interesting now is the fact that Google is building one. Consider what happens: there are certain coefficients in probability theory that needs to factored in when arriving at a probability decision. These factors are usually computed (and fine-tuned) using past history. Google has the resources to implement a large-scale prediction market. Therefore, it will possess these magic coefficients. In addition to knowing what is happening (aka Google News), it will finally know what is going to happen.
"42" does not seem to be so funny after all.

Read more!

Ebay + Skype = Semantic Web - Google ?

9/16/2005

There has been widespread consternation and disbelief over the sale of Skype to Ebay for 4.1 billion dollars. Muchos dineros in my opinion. Even Robert Scoble tries to make sense of it all.
But in my opinion, they have all got it wrong.

Before I go any further, let me tell you who founded Skype - Niklas Zennström and Janus Friis. Two guys who also wrote software to share files and gave the recording industry a severe case of ants in their pants. Given that Skype is an "inflection point" (I seem to be quoting Andy Grove a little too much these days)for incumbent telcos, it leads to reason that there were other, more eligible suitors for Skype in the very relevant and related field of telecom voice carriers.
But they gave it up to Ebay.

Now let us look at a very relevant question - Who is the biggest threat to Ebay? It's not rival auction sites, it is not brick-and-mortar liquidation houses, it is not entities like Amazon zShops. It is Google... or whoever among Google, MSN, Yahoo is going to win the search war.
People "google" for stuff, they never "ebay" for anything. Google is now the defacto standard for our collective intelligence. It is Cerberos holding the keys to everything.
It is a very, very trivial matter for Google to setup its own auction house and the scaling up of its business will rival Ebay's in a much shorter time. Given that Google has shown keen interest in setting up a monetary transaction system to rival Paypal ( and given the fact that half the people are fed up with Paypal - check out the Katrina Relief fiasco) and it wont be surprising if they create something simply too good to be true.
All this is setting up stage for a direct confrontation with Ebay. There is no way in hell that Ebay can create a search engine to rival Google.
Now what?
Two pieces of a jigsaw puzzle - Gmail and Skype. How could they possibly be related, you ask? Ahh but sire, therein lies the key. Gmail has set a precedent that could I like to call "non-invasive invasion of privacy". In other words, targetting advertisements related to the actual contents of my very private emails. Is it too difficult to carry this over to voice? Is it too difficult to integrate sophisticated AI on the Skype software to deliver targeted ads? And since Skype already manages to keep your telephone calls private, routing them through your neighbors computer, it is not difficult to add some semblance of privacy to these targeted "advertisments".

The war here will be fought on battlegrounds of technology as well as legal hallways. Currently VOIP does not come under the purview of regulators - which gives Ebay+Skype some breathing space. But in that time, if they can come up with a legal shield that will allow them to do this, it will all but cut off Google from their channels of distribution.
Building up Skype as the world's leading provider of VOIP is part of the package. That will allow Ebay to reach into homes and tap into your conversations. You could be telling your buddy that you were thinking of buying a not-too-expensive pearl necklace for your girlfriend, and suddenly Skype's software queries Ebay for "cheap+pearl+necklace". The results could be delivered via SMS, Email or by a tele-marketer.
While online advertising has a good enough conversion ratio (converting clicks into actual purchases), this would beat the pants of everybody.

In my opinion this is a mighty fine gamble that Ebay has taken. And I'm surprised no one else has speculated this way (Robert Cringely, are you listening??)

Read more!

Just a brain teaser

9/09/2005

There is a very interesting puzzle which you would be able to find at several places, but I have an interesting non-trivial twist to it:

Part 1: There are 12 balls, one of which is lighter than all the others. Can you find out which ball in 3 weighings?

Divide the 12 balls into 2 groups of six. Weigh to find the lighter six balls. Divide 6 balls into 2 groups of 3. Weigh to find the lighter 3 balls. Weigh two balls - if they are equal, then the third ball is lighter, else it is the lighter of the two.

Part2: Same question as above, except now you dont know if the ball is heavier or lighter.

Divide the 12 balls into 4 groups of three balls each. weigh two groups - thus locate the 6 balls(in two separate groups) which contain the "Ball"; Also note which group goes up and which group goes down in the weighing balance. Weigh one candidate "Ball" group with the known good balls group - this way you find out which group contain the "Ball" - at this point of time, you also know if the group was the "up" group or "down" group, therefore whether the "Ball" was heavier or lighter. Now the three balls can be resolved as above.

My take on this:

Part3: Same question as Part2, except can you do with an initial group of 4+4+4. i.e. in the first weighing, you are forced to weigh 4 vs 4 balls.

I believe this is a non-trivial solution to this and dunno if anyone else has attempted it.
Weigh 2 groups-of-4. If they are both equal, then the "Ball" is in the third group. This can no be made a 6 ball group by adding 2 good balls. The solution now follows Part2 above.
If they are unequal - note which is the "up" group and which is the "down" group. Here's the complicating part:

**** ???? <- let these be the 2 groups of balls
remove 2 balls from group-1 and 1 ball from group-2. So,

** ??? **?
Now there are group-1, group-2, group-3.

Put 2 balls from group-2 into group-1 and pad group-2 with 3 good balls.

**?? ?000 **?
Weigh group-1 and group-2. If the direction of "up" and "down" has changed from previous weighing, then the fault is because of the two ?? balls transferred from group-2 to group-1. If the directions are maintained then the fault is because of the two ** balls in group-1 and ? ball in group-2. Thus now u have 3 balls - **?
If the weighing is equal, then the problem is in group-3, again ending up with 3 balls - **?

Now, we already know that * balls and ? balls belong to one of "up" or "down" group.

From the 3 balls remaining, take one * ball out, and club the remaining * and ? balls together. So,

* *?

Weigh the *? ball with two good balls. If the *? goes in the direction of *, or in the direction of ? ("up" or "down"), we know whose fault is it. If they are both equal, the remaining * ball is the culprit.
The interesting thing is in the last possibility - we will never know if the ball was heavier or lighter!

You heard it here first!!!

Read more!

DAtum

Delhi Half Marathon Training: Week 1

Chapter 71

Does heapsort make more sense for EDA algorithms ?

Prediction markets: real life psychohistory?

Ebay + Skype = Semantic Web - Google ?

Just a brain teaser

Author

Categories

Posts

Archives

Tech Blogroll

Business Blogroll

Sights and Sites