Google killing IP lookup websites
Posted on | October 30, 2011 | No Comments
Google is being evil nice by providing some a new feature from it’s search engine.
Times and again, computer users behind some private network needs to know what is his/hers external IP address? I have needed the information numerous time, whenever Comcast decides that I need a new one. Typically I’d google the phrase “what is my ip”, to which google would typically return www.whatismyip.com as it’s first result, and I would click it.
Today was my most recent incident of such time. Upon posting my query, to my surprise, google has decided that they’d spare me the extra click to my trusted site. Check this out!
Thanks, Google! 
The Search Space of Ramsey (5, 5)
Posted on | October 29, 2011 | No Comments
I think any theoretical computer scientists (or students) who have heard of Paul Erdos and Ramsey Numbers are tickled by the well known problem of Ramsey (5, 5).
Ramsey numbers intrigues computer scientists because of the concept seems very simple to understand, but the complexity of the problem is super-exponential. While we know that Ramsey (3, 3) is 6; the search space is quite small that it can be exhausted in one sitting; it may take us a while to find the value of Ramsey (5, 5). That ‘us’ is not just you and me, but our descendants too. And it’s probable that humanity may never know the exact value of Ramsey (6, 6).
Our dear Paul Erdos famously quoted by a friend, Joel Spencer:
“Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.”
For the casual reader who are still reading, here is the obligatory, standard, and surprisingly simple introduction of Ramsey number. Imagine a group of any 6 people in a room, it is guaranteed that there are 3 mutual acquaintances, or 3 mutual strangers. Just run a few iterations in your head on how you’d set up random 6 people and theirs who-knows-who relationships; the property above holds true. For a formal proof of this, follow the following link.
The casual definition of Ramsey Number R (k, l) is simply the smallest number of people where it is guaranteed that k people are mutual acquaintances or l mutual strangers. The formal definition is defined as the smallest complete graph (clique) where any 2-colloring of the edges, pink and yellow, will guarantee the existence of a complete pink sub-graph of size k, or a yellow sub-graph of size l; but who really cares for formality? Ramsey believes that for any k and l, such number exist.
Ramsey (5, 5) is the smallest number of people where we can guarantee 5 mutual friends or 5 mutual strangers. It doesn’t seem to be above our imaginations; we surely have been in many gatherings where we’d find 5 mutual friends, or 5 mutual strangers. But what is the exact smallest number such requirement is guaranteed ? As of now, we know that the value lies between 43 and 49 people, again seems to be innocent enough, so what’s the big deal, really? There lies the trap to the naivete like me.
To prove that Ramsey (k, l) = m, we need to show that:
- For any possible acquaintance configurations of m number of people, we can find k mutual friends or l strangers. This is to show that m is sufficiently big for R (k, l ); mathematically R (k, l) <= m.
- There exist some (just 1 is enough) acquaintance configuration of n = m – 1 number of people where we cannot find k friends and l strangers. This is to show that m – 1 is too small for R (k, l); mathematically R (k, l) > n = m – 1.
- Once you can show both, we find that m – 1 is too small, but m is big enough, so R (k, l) must be m!
So I really want to know how much effort is needed to really crack this problem, I did some basic number crunching.
Let say we conjectured that R (5, 5) is 43. We know from previous works by experts that 42 is too small, so simply need to show that 43 is big enough. Formally, we need to show that all possible 2-colloring of the edges of complete graph of size 43 that we’d find complete sub-graph of size 5 of one color or the other. All good!
But how many possible 2-colorings are there? First, I computed that a complete graph of size 43 has 903 edges, good. Now how many ways can we 2-color 903 edges? It is basically 2 to the power of 903; again, I computed and I got:
6762169998536515153309949246931412563441245773262355483237 8970755414259527260782012725408753620120050518322559136912 4708969404876163437487680689892432562658442734955518726507 7359763426258258445478710181225103211573094762147219990257 1314803042180668990660938354910463787008
Bam! That is a 272-digit number! Let’s pretend that we’d use our computer, and we can validate 1 configuration per 1 millisecond. That means that we can validate 1000 (per second) * 60 (per min) * 60 (per hour) * 24 (per day) * 365 = 31536000000 configurations per year. We would need 2.144 * 10^262 years! Warning, that’s not in the vicinity of 262 hundred years, it’s in the vicinity of 2 or 3 googol years! So even if all computers owned by Google is used to for this, we are still far far faaaaaarrrrr away from it.
I think Erdos was being optimistic with his alien story. I’d say if such aliens do come and demand R (5, 5), we should just send Russel Peters, Anjelah Johnson, and Colbert to negotiate the terms. Maybe they’ll laugh and mellow out.
Epilogue. Stanisław Radziszowski is a mathematician who has been a diligent curator of all things Ramsey. He publishes his findings in here. He should probably accompany our pack of comedians to meet the aliens.
R.I.P Steve Jobs
Posted on | October 5, 2011 | 1 Comment
See the following statement from board:
CUPERTINO, Calif., Oct 05, 2011 (BUSINESS WIRE) — We are deeply saddened to announce that Steve Jobs passed away today.
Steve’s brilliance, passion and energy were the source of countless innovations that enrich and improve all of our lives. The world is immeasurably better because of Steve.
His greatest love was for his wife, Laurene, and his family. Our hearts go out to them and to all who were touched by his extraordinary gifts.
SOURCE: Apple
Apple Katie Cotton, 408-974-7269 katiec@apple.com Steve Dowling, 408-974-1896 dowling@apple.com
I have never met you, but you are such a role model. Thank you for your Stanford address.
You will be deeply missed.
What happened to the goose?
Posted on | October 8, 2010 | No Comments
Once I watched a video on Vinod talking about his former future partner, Andy Bechtolsheim. Andy was licensing his SUN I prototype for $10K. Vinod, though, said that he doesn’t want to license it, he want’s Andy! Here is one great maxim from him, “I don’t want the golden egg, I want the goose that lays golden eggs!”
I was imagining a conversation with him with regards to the goose that lays golden eggs; heck, maybe even diamond eggs, but are lazy to lay. I’d spare you the details but in China goose that don’t lay eggs gets to sit on a plate.
Monetary issues
Posted on | October 5, 2010 | No Comments
Just so that I have a new blog post, and so that I can feel a bit better..
(10:52:35 AM) slingman: heads up fools…. merging trunk back 1.2.2 in progress
(10:55:20 AM) slingman: conflict on jquery.detailschapter.js
(10:55:23 AM) slingman: whose code is that?
(10:57:14 AM) michele: R8797
(10:57:16 AM) michele: karthick
(10:57:21 AM) michele: i mean r8797
(10:58:04 AM) nac: whats the conflict?
(10:58:31 AM) ez_man: monetary issues
Embedded Video Support in ePubs
Posted on | July 23, 2010 | No Comments
Videos in ePubs? Are you serious?
Well, eventually our books will look like the newspapers in Harry Potter movies (MPal, 2010). Just imagine, not just static images to embellish the text, but also the motion pictures and sound of people screaming and yelling in Azkaban.
But are we there yet?
This is what I found from a short googling on the matter. This is what I know to be true by Summer of 2010.
- Video and audio files are not part of the core media types that are supported per the current ePub standard (IDPF – OPS 2.0.1). However, the standard allows for embedding non-core media if an alternative core type is specified as a fallback. The result is that currently some readers support media types that other readers don’t. See the standard page.
- Apple iBooks can play embedded video in 3gp and m4v using HTML5 notation. See:
- Bookworm is web-based reader, and it supports ePub with embedded flash video. See: http://blog.threepress.org/2009/11/14/using-flash-video-in-epub/
- Sony Reader doesn’t support video.
- Comprehensive report on video and audio support on different readers are not yet to be created. This issue is tabled for later.
- Linking to resources outside of the ePub bundle is not suggested, but may not be fully restricted, if alternative media available. I know from previous experience that Bookworm and Calibre allows external media. However, iBooks on iPad crashed on some sample with external links without alternative embedded media.
Transparency
Posted on | May 19, 2010 | 1 Comment
Successes should be celebrated
Mistakes should be corrected
Failures should be learned from
Cover-ups should be punished
Simple Recipe for PDF Stitching
Posted on | April 28, 2010 | No Comments
I found this little recipe on how to merge several PDF documents into one, using Ghostscript. Super simple:
gs -dNOPAUSE -sDEVICE=pdfwrite -sOUTPUTFILE=merged.pdf pdf1.pdf pdf2.pdf . . . pdfx.pdf
Several other recipes can be found in here: Putting together PDF Files.
Cloudy, with a Chance of Fish. Literally !
Posted on | March 3, 2010 | No Comments
An interesting reading I got this morning was about a small town of 700 in Australia, Lajamanu, that had an interesting rain. A fishy rain!
While quite freaky, apparently fish rain is not too rare, a documentary video below accounts about 600 occurrence in a year. The interesting thing about this one is that the nearest body of water the battered town is a river 326 miles away! You can follow the complete story from this publication.
Git resources for svn users
Posted on | March 2, 2010 | No Comments
Many Subversion (svn) users are jumping the wagon to the coolest new kid in the source code management tool block, Git.
Git does provide a lot of improvements over svn, but it can be very unintuitive at times. These two are more different than they are alike, so it’s just wouldn’t work to simply use git while thinking in svn mindsets.
Git is first and foremost, distributed SCM, while svn is a centralized one. When you clone a git repository, you’d get a complete repository, not just a working copy! Since your local copy is a full repository, you’d commit your changes locally too! Only when you need to share your changes to the world would you push to external repository.
A few documents have help me ease the transitional pain. Hope these helps you too:
Tags
Meta
Liking what you read?
