The traveling salesman problem (TSP) is a very simple combinatorial optimization problem. Given a set of cities and distances between each pair, the problem is to find the tour of least distance that travels each city exactly once. Simple – as in simple to state. But from what I have seen this seems to be the hardest of the hard problems to solve. To give some background, there are these famous hard problems in Computer Science that do not have “efficient” solutions. Brute force solutions work very easily on them, but take an eternity to run. In spite of 40 years of extensive research by some very smart people, brute force seems to be the only solution. For example, the TSP can be solved by listing all possible tours covering the cities once, and picking the one with the least length. This takes an eternity as there are an exponential number of such tours (n!). These problems are the (in)famous NP-Hard problems. Stephen Cook at the University of Toronto proved that if one of them can be solved efficiently, all of them can be!!! A very intuitively pleasing fact. ...

I, like most others, did not have a choice when I first chose a religion to follow. I was….er….born into one. After spending quite a while seeing it being practiced, practicing some of it myself, defending subtle nuances in quasi-intellectual arguments with friends, thinking about it for quite a while, I gave up on conventional religion. This decision was driven by conscious rational thought and emotionally charged events. From the outside, this gave me a chance to look at religion as a concept. I respect conventional religion for its ability to give solace to helpless minds. There have been times when I wished I could enjoy religious comfort. I am amazed at how religious thoughts have united various peoples across time. One’s belief in religion constitues a big amount of one’s identity. ...

I was told once that we make a lot of special days: Birthdays, Anniversaries, Valentine Day, New Year’s Eve, etc. We expect a little too much these days, we want things to turn around from how they are, and suddenly become utopian, we want surprises, we want perfect days. All this, all the while sets us up for some kind of disappointment at the end of the day. Sometimes, the foreboding thought that expectations will not be met is enough to induce sadness. ...

I am mostly someone else to the world. I am not what others consider I am. This might be true with most of us, but what surprises/saddens/shocks/intrigues me is that I am mostly someone else to myself. A simple question settled my doubts on this regard. How many times have I told myself that I was good (bad) at something because of some (lack of) intrinsic ability, while time and experience had shown me otherwise? I have fooled myself many times this way. A game of football, chess, academics, work, physical abilities, and mostly – events of everyday life and my having total control over all of them. Everyday events are strange; they don’t mean much in the long run, but they have shown me that my level of control over things are somewhat hazy, mostly absent. I don’t have full control, but it doesn’t seem to matter very much. ...

I am listening to Tere Bina Zindagi Se Koyi Shikhwa Nahin from Andhi, sung by the I-can-so-imitate-him-but-he-still-remains-elusively-inimitable Kishore Kumar and Lata. It is so easy to lose myself in this song, in the lyrics, and in all those emotions and memories that take over and transport me someplace else. This particular song has a curious mix of pathos and elation. The protagonists feel bad about the lost years that they couldn’t be together, but in their glances and gestures they display a love which transcends age and which speaks of a hope about the future. This paradox of emotions is captured in the first 2 lines of the lyrics – ...

I have never heard the Who’s music; and scientists have always wondered about the Why’s; Science mostly explains the How’s; Today’s question is the What. On first glance, the What appears to be tame compared to its illustrious peers. While beginning Jaynes’s tome on probability, I came across this quote said around 1948 and attributed to von Neumann – “For those who believe that comptuers cannot do all that we humans can; please explain in finite, precise steps, what it is that you can do; I will make the computer do precisely that.” ...

ended up being this. Do check out Cosma Shalizi’s Notebooks. What amazes me is the amount of reading a person can do. And the diverse range of reading interests anyone can hold. This is by far the widest range of reading that I have seen anyone accomplish. I wonder where time passes us by. Passed me by. I need to rework my schedule. In other news, Aishwarya Rai has been asked to present an Oscar. Why her? and why this? Of course, she is beautiful, artsy, speaks good English, hazel eyes, brown hair, high cheek bones, the works. First, Cannes, and now Oscars. I guess she is just what the media wants; here, as well as in the west. The clueless reader from Bangalore will be proud about how India has finally arrived on the World Stage and fold Bangalore Times, finish her donut, exit a Starbucks like coffee shop, and don her headphones, and become Melanie again. ...

Currently a very heated discussion is on in the IITB.general newsgroup here at IIT-Bombay. The topic is somewhat pertaining to the lack of academic and research interest of undergraduate (UG) students (as compared to postgraduate (PG)), and their building interest in extra-curricular activities. Replying to the “IIT-B.Tech-praised-by-press-across-the-world” comment by some UG, one of the professors replied that both the Indian and the US presses are biased and self serving, or serving some kind of big-brother of sorts. These presses want go glorify BTech education in IITs, and not bother about MTech and PhDs, and esp any form of research conducted in IISc, and IITs. Why is it that we never hear about IISc in the Indian Media? Is it cuz it is sub-standard? Think again! ...

The Indian Railways is so fascinating. Mesmerising legacy, mindboggling scale, unbelievable efficiency and of course, the romance of a train journey. My earliest memories of train fascination is that of Gopi: a very close friend from high school days. He used to rattle the starting and ending stations of all train names from the Railway Timetable. Believe me, I used to actually quiz him with that book. There is this very cooL urban legend about Gopi that made its rounds in our high school corridors (I think its due to Dhruva, but he might claim innocence, like always ;-> ). Legend has it that when some friends had been to Gopi’s place to call him for a customary game of cricket. Gopi and his brother were all dressed up and ready to go somewhere. They were pestering their father about how they would be late for some train and would miss it and all. The unsuspecting friends assumed that their pal was going out of station or something, and decided not to include him in the next day’s game. But it so turned out later (much to their amazement) that the party was going to the Bangalore City Railway Station not to travel soemwhere, but to check out some train that would halt there for some half an hour, and had some “cool” technical specification!!!. Whoa, now, that is a true enthusiast, considering that we were around 12 that time, and his brother was barely 10. Imagine being 10 and being interested in Railway Gauges. Anwyays, thats just the legend. I wonder if Gopi still has his passion for Indian Rail. ...

Its been a while since I have blogged anything technical. These days, I am working on the open source search engine, Nutch. Before I get into what I am doing, let me explain why, in the last sentence, I put the phrase “open source search engine” as a part of the href tag. Search engines use anchor text extensively to figure out what a page is about. For example, the home page of Tejaswi doesn’t have the phrase “home page” anywhere. So, by looking at the anchor text of all the in-links to a page, the search engine figures out what the content of the page might be about. This is a latent way of identifying the content of a page: by looking at what in-links call it. Now, when I say “the open source search engine Nutch” in the anchor text and link to nutch.org, that phrase gets associated with the site, and helps someone searching for an open source search engine, but has no clue about Nutch itself. ...