Parameterized Complexity and ETH

Note: Cross-Posted from the complexity-theory class at CMU :)

After another long hiatus, on the day yet another semester got over, we look into Parameterized Complexity theory (introduced by Downey and Fellows via many papers) and its connections to classical complexity theory specifically via the Exponential Time Hypothesis (of Impaggliazzo and Paturi 2001) in this post. Parameterized complexity provides a framework for a more refined analysis of hard problems. Heuristics, parallel algorithms, approximation schemes, randomized algorithms are some of the approaches used to counter such problems. But these approaches suffer from many defects ranging from no hard bounds on the quality of the solution (heuristics), to not being applicable to really large instances (parallel algorithms) to impractical solutions (like some PTAS's etc.).

Introduction:

Classical complexity classifies problems using the concept of some resource (time or space). This leads to a good theory but it also ignores any structural information in the input which makes problems appear harder then they really are. There is a wide variation in the worst-case complexities of known exact algorithms for the NP-complete problems. For e.g., there are pretty good 3SAT solvers present right now which scale to a large number of variables.

Parameterized complexity tries to explain these differences by assuming that there is some part of the problem (the `parameter') will be small and allow us to develop efficient poly-time algorithms. The classic example for this is to consider a database query - it has two parts the database and the query of which query is usually much smaller than the database. The query size $k$ would be the natural paramter for a parameterized complexity analysis by admitting algorithms whose non-polynomial behavior is restricted by the parameter: if $k$ is small and $n$ is large, $O(2^k . n)$ is better than $O(n^k)$.

The main contribution of the theory is establishing the intractability of certain problems by classifying problems into complexity classes by reductions which are inherently 2-dimensional depending on the problem size as well the parameter. A problem can have different parameterizations also, each leading to different results.


Complexity Classes - FPT and the W[t] hierarchy:

A parameterized language $L$ is a subset of $\Sigma^* x \Sigma^*$ where $\Sigma$ is a finite alphabet. Let $(x, k) \in L$, then we call $x$ the main part and $k$ the parameter.

a) Tractability - Fixed-parameter tractable (FPT): $L \in FPT$ if it can be decided in time at most $f(k) . x^{O(1)}$ for an arbitary function $f$. For a fixed $k$ it is in P, moreover for every $k$ it is in the same polynomial class via the same machine. As an example, consider the $p-SAT$ problem where given the formula $\phi$ and the parameter $k = $ number of variables in $\phi$ decide whether $\phi$ is satisfiable. This is clearly in FPT as the obvious brute force approach for formula of size $n$ with $k$ variables will take time $O(2^k . n)$. There are many real world problems which are in FPT like parameterized Vertex Cover which uses the kernelization technique to get a $O(k . n + 1.286^k)$ algorithm (due to Chen, Kanj and Jia, 2001). Note that the classical Vertex Cover is NP complete - yet this result shows that it
is not as `hard' as say Independent Set.

b) Parametric Intractability: Analogously to classical complexity theory, Downey and Fellows developed a completeness program for intractable parameterized problems. In order to compare the hardness of parameterized problems, we need a 2-dimensional reduction (called `parameterized-reduction'). Roughly, a language $L$ is parameterically reducible to $L'$ if there is an FPT algorithm that transforms $(x, k)$ to $(x', k')$ so that $(x, k) \in L$ iff $(x', k') \in L'$ and $k' = g(k)$ where $g$ is an unrestricted function. Note that Karp reductions are rarely parameterized reductions (e.g. Clique to Independent Set is one of the exceptions).


1) W[1]: The lowest class of parameterized intractability can be defined as the set of languages that are reducible to the Short-Turing Machine Acceptance problem (also called the $k$-step halting problem) where we want to determine for an input consisting of a nondeterministic Turing machine M and a string x, whether M has a computation path accepting x in at most k steps. In some sense, this is the parameterized analogue to the Turing machine acceptance problem: the basic generic NP-complete problem in classical complexity theory. Canonical problems include Independent Set (does $G$ have an independent of size $k$), Weighted 3SAT (does $\phi$ have a satisfying assignment of weight $k$) etc. We will also give an alternative definition of W[1] afterwards which is actually used for the basic results.


2) The W[t] hierarchy: Interestingly, while general $k-$SAT and 3SAT are equivalent for NP-hardness in classical complexity, there is no known parameterized reduction computing general satisfiability from 3-CNF formulae. This leads to a realization that the logical depth of a formula affects its parameterized complexity. Intuitively it is related to the number of alternations between unbounded fan-in AND and OR gates. Hence, we can base the hierarchy on the complexity of circuits required to check a solution.

The W[t] is based on Circuit-SAT problem (parameterized by the weight of input like for Weighted 3SAT) for family of circuits $F_{h, t}$ having:
1. Small gates: with constant fan-in
2. Large gates: with unbounded fan-in

and of depth $h$ (max. number of gates in the path) and weft (max. number of large gates in the path) at most $t$. Clearly, we have the containments:

$FPT \subseteq W[1] \subseteq W[2] \ldots $

It is not known whether the containments are strict or not. Note that W[1] can now be defined as the class that can be reduced to an parameterized Circuit SAT on the family of constant depth weft 1 circuits. Downey and Fellows (1995) proved that parameterized Independent Set is W[1]-complete. The hardness proof is very intricate and we omit it here. Note that using this definition it is easy to see why Independent Set is in W[1] (sketch):
1. Each vertex in $G$ corresponds to one input gate in the circuit
2. For every edge $(v, u) \in G$ build a small OR gate: $(1-v) \wedge (1-u))$
3. Output from small gates are given as input to a single large AND gate.

Interestingly unlike NP-hardness results, W[1]-hardness for the $k-$Halting Problem uses Independent Set completeness as intermediate results. There have been many papers demonstrating naturally occuring W[t]-complete problems like Dominating Set for W[2] etc.)- for an extensive list of already classified problems see the Downey and Fellows monograph.

Exponential Time Hypothesis (ETH)

ETH was first studied by Impagliazzo, Paturi and Zane 2001 and it states that 3SAT $\notin$ DTIME$(2^{o(n)})$, where $n$ is the number of variables. They also proved that the hypothesis is robust to analogous hypotheses for other NP-complete problems like Independent Set etc. In fact, they also showed that the ETH is independent of size measure: 3SAT is solvable in time $2^{o(n)}$ iff it is solvable in time $2^{o(m)}$ for input size $m$. Note that this suggests that weighted 3SAT should also be intractable for `any parameter'.

Connections with Classical complexity:

The above paragraph suggests that ETH and parameterized complexity might be related. In fact they are and Chen and Grohe recently proved that ETH and paramterized complexity theory are isomorphic by an explicit reduction preserving isomorphism. We don't show that here, instead we prove a simpler result that yet provides a strong link to ETH (proof is a version from Downey, Castro et. al 2003 and uses parameterized miniaturization and is different from the original proof by Abhramson, Downey and Fellows):

Theorem: If FPT = W[1], then ETH fails i.e. 3SAT $\in$ DTIME$(2^{o(n)})$.

Proof: We use the equivalent definition of ETH based on simple Circuit SAT. The idea is to capture the ETH perfectly in a parameterized complexity class. The starting point is the Mini-Circuit SAT problem which is a parameterized miniaturization of simple Circuit SAT:
Input: Positive integers $k$ and $n$, and a Boolean circuit of total size at most $k\log n$.
Decision: Does there exist any $x$ for which $C(x) = 1$.

Note that the parameter here is $k$. Also, trying all possible inputs gives a brute force $O(n^k)$ algorithm. Next we give a cruicial lemma due to Cai and Juedes 2001. It essentially fully characterizes the ETH with a complexity class in parameterized theory.

Lemma 1: Mini-Circuit SAT is in FPT iff ETH fails.
Proof: One direction follows from the brute force algorithm and noting that $2^{o(k \log n)}$ is a FPT function.

Now suppose we are given a boolean circuit $C$ of size $N$ and that Mini-Cirsuit SAT is solvable in FPT time $f(k)n^c$. Set $k = f^{-1}(N)$ and $n = 2^{N/k}$. In general $k = f^{-1}(N)$ will be some slowly growing function of $N$; so $N/k = o(N)$ and also $cN/k = o(N)$. Hence using the FPT algorithm for Mini-Circuit SAT we have a running time for Circuit SAT as: $f(f^{-1}(N)) (2^{N/k})^c = N 2^{cN/k} = 2^{cN/k + \log N} = 2^{o(N)}$.
Thus ETH fails. Proved.

Now lets define the complexity class MINI[1] to be the set of languages that are FPT reducible to Mini-Circuit SAT. It turns out that many $k\log n$ miniatures of familiar NP-complete problems are MINI[1] complete (Downey, Fellows et al. 2002). It is easy to see this because essentially all the usual NP-complete reductions of Circuit SAT to these problems work as FPT reductions because they were also linear size reductions.

We concentrate on the Mini-Independent Set problem. Surprisingly, it can be reduced to the usual parameterized Independent Set problem.

Lemma 2: Independent Set parameterized by the size of independent set is MINI[1]-hard.
Proof: We give a Turing reduction. Let graph $G = (V, E)$ be the miniature, for which we wish to determine whether $G$ has an independent set of size $r$ with $V \leq k\log n$. We can think of verices of $G$ as organized in $k$ blocks $V_1, V_2, \ldots, V_k$ each of size $\log n$. So for each possible way of writing $r$ as a sum of $k$ terms $r = r_1 + r_2 + r_3 + \ldots + r_k$ with each $r_i \leq \log n$, we have a turing reduction branch which represnts a commitment to choose $r_i$ vertices from the corresponding block $V_i$ to be in the independent set. The total number of branches are $(\log n)^k$ and again it is a FPT-function.

For each branch, we produce a graph $G'$ that has an independent set of size $k$ iff the miniature $G$ has an independent set of size $r$ distributed as indicated by the commitment made on that branch. The graph $G'$ consists of $k$ cliques with some cross edges. The ith clique consists of vertices in correspondence with the subsets of $V_i$ of size $r_i$. An edge connects a vertex $x$ in the ith clique and a vertex $y$ in the jth clique iff there is a vertex $u$ in the subset $S_x \subseteq V_i$ represented by $x$ and a vertex $v$ in the subset $S_y \subseteq V_j$ represented by $y$, such that $(u, v) \in E$.

From Lemma 2 we can conclude that $FPT \subseteq MINI[1] \subseteq W[1]$. We just need to observe now that if FPT = W[1] it implies $M[1] \subseteq FPT$. By Lemma 1, ETH fails.
Proved.

Discussion:

The above result hints that FPT vs W[1] problem is like the P vs NP problem of classical complexity theory. In fact it was also proved by Downey and Fellows that FPT $\neq$ W[1] implies P $\neq$ NP. But it is not known that if FPT $\neq$ W[1] implies anything about the rest of W[t] hierarchy. Importantly, practical intracbility of problems in NP, which are unlikely to be complete for NP, can be shown using W[t] hardness results. Parameterized complexity has deep connections to other complexity results as well. Just recently (a week back) Galesi and Lauria showed a connection with Proof Complexity based on randomized algorithms for W[t]-hard problems. The field is very active and there are many papers and surveys being published in it.

Mumbai

I spent four wonderful years at IIT-Bombay pursuing my undergraduate studies. The times were good, I was carefree and world seemed to be a better place then. But this post is about Mumbai the city - from an outsider who is not a Marathi manoosh :) This looks to be a good time after the movie Slumdog Millionaire which was based in Mumbai has swept the Oscars.

I never quite understood Mumbai as a city. When I first came to Bombay (as it was called then), it was raining cats and dogs, roads were full of sewage, auto-rickshaws were driving with death-defying deftness, my luggage was fully wet, and my dorm room was at the ground floor with the brown water threatening to flood it. IIT-B itself from outside looked like a dilapidated cloth mill.

Bombay is full of peculiarities. For most parts, I didn't use to venture out of the campus - out of fear of getting lost! Well undergraduate life is demanding, so I had to go out for passport, a desktop computer etc. etc. Desktop computer took me to the red-light area of Bombay while passport office was in the posh area of Worli full with hip-hopping teens (it has a big Ganesha temple as well). Funnily enough, typical of Bombay, it is very easy to cross from Worli to the shady area without knowing (I learnt it first-hand unfortunately). I had to take the local trains for my travels. Traveling in locals at Bombay makes you ready for anything in life. You are so close to people that you can have to take in the smell of their sweat! Once I was stranded on the stairs as the platform was too full of people - you just could not go in! And local trains go through some pretty amusingly named stations - sample Chinchpokli, Kandivili, Borivili, Sion, Bhandup etc. etc. And for good measure, Mumbai's airport is ranked as the worst in recent surveys. Every year the city drains clog making the stench outside somehow reassuringly familiar.

So, what was there to love? First you just wonder at the sheer magnitude of humanity in this city. There are just too too many people. Your eyes get saturated to be frank. I think no other city in India can match Mumbai in this (except possibly Calcutta).

Secondly, the filth and squalor. It is hard to miss the abject poverty of many people. You go out and usually run into scores of people begging. Although poverty is disconcerting and has an universal appeal (go to the 'depressed areas' in New York City, LA, Pittsburgh etc. and you would know), poverty in Mumbai has a different feel. Yes, you have the usual criminals and beggars and robbers but you also have the inescapable hard workers who dream of breaking the shackles and making it big. The level of poverty in Mumbai is truly shocking in some areas. But yet, life goes on - they sell kid's color pencils on the local trains, sell beads on the platform, sell flowers whenever your taxi stops at a red-signal...

And with all this depressing reality Mumbai's glitz is like no other in India. It is the commercial and entertainment capital and a leading educational center (with a IIT, BARC and TIFR). Leading men of business, science, politics, glamor call Mumbai as their home. Mumbai has the choicest of restaurants, hotels, complexes, parks putting any city to shame. Mumbai's landmarks offer the unquantifiable quality of hope and aspiration. It is sometimes hard to not to wryly laugh at this disparity. When you are landing in the Mumbai airport, densely packed rows of slum houses welcome you on both sides of the runway. But get out of the airport, seven star hotels and chauffeurs jostle for your luggage. I always used to wonder - where did the slums disappear suddenly!? Has Mumbai mastered the art of turning the other way?

Fortunately not. Mumbai is easily the most 'humane' city I have ever visited. The inherent level of altruism in Mumbai is surprisingly high. I was once talking to an autorickshaw driver whose vehicle had been badly damaged in the rains. So, I guessed he must be cursing the rains (which are actually pretty pretty bad - the small showers that are passed off as heavy downpours here are another matter!). But in his opinion was the rains were necessary - he is thankful for them - rains keep the Mumbai lakes full of drinking water, and helps the cultivators to grow fruits and vegetables.

I think the local trains have a vital role in leveling the playing field. For most of Mumbai's people, locals are the only affordable way to go from Point A to Point B daily. Executives, contractors, labor or even beggars share the coach. No special treatment. This is quite remarkable as the differences between have and have nots are only too stark elsewhere. The cosmopolitan nature of the city ensures that outsiders and even occasional visitors get assimilated very soon. Mumbai people easily win hands down for being the most helpful people in India. People genuinely try to give you a helping hand. Accounts of heroism in Mumbai in the innumerable tragedies it has so stoically faced are indeed unparalleled. And it is the only city I have been to date where the autorickshaw drivers are not out to fleece you! Indeed, the endearing image of Mumbai is that of the people.

I guess Mumbai allows people do what they please and just live! It offers something for everyone from your slum dweller to your average multi-billionaire to your academic. The city is free of shackles induced by complex rigid histories and unnecessary social barriers that stagnate all too many cities in India. It has made all of them irrelevant to the pressing need of the immediate. It represents the epitome of human drive, hope and magnanimity amidst unbearable wretchedness. Mumbai symbolizes the oasis in the desert. What is there not to love?

---

To end, a humorous post on the demanding skills of basic arithmetic :)

Quotable Quotes

Hello, after a long hiatus.

From our in-house mavericks (note: more fun if said with correct intonation):

• Numbers mean nothing to me.
• CMU is lucky.
• This is Ali. Please leave a message.
• How could I have missed the fruits - esp when they are low-hanging.
  
• Dude, I don't talk puns.
  
• I am super-awesome?
• No.
• Dude, is there water in the bathroom? I am also coming!
• Die. Man. Die. Go Fish.
  
• And so we can unlock the mystery behind AIDS.
• Naaaa, my back hurts, while sitting.
• Sorry Man, sorry!
• Ohh 67F - I am going home!
• Cucumber-Mint Yogurt. Bowl.
• Bhaiyya - aap single hoh?
• Didi- aap single hoh?
• Ohh you got A-? But I thought everyone got A?
• Please warm the cache, thanks.
• Buddy I only used buddy, don't worry buddy.
• OK. That was an awkward pause.
  
• Randomly submitted da.
• Same shit. Different era.
  
• Precis mon. Bum.
  

Try guessing the person for each quote. :)

Cricket, Pets, Tickets and Landlords

Apologies for an extended break from the blog! (does it matter though? The most qualified wean-hall-floor-mopper ever, good friend Samir, thinks it does :-)). As usual, the realities of a harsh semester catch up with you pretty soon.

Although my awesome OS project with two hardcore computer-systems guys (Ravi and Ali) has unfortunately captured my rather limited imagination, I have been able to devote some time to other less challenging activities in life.

Like following your national cricket team. The Indian cricket team rolled over the Aussies in the 2nd Test match in such a fashion that it was breathtaking. It had been a long time coming but the Aussies finally got what they had been dishing out to other cricket teams for almost a decade now. And it was pure pleasure! :D. The cricketing world is small (at least in the number of countries that play it). Sadly, even in the country that invented and spread it over all its dominions, England, the game is firmly behind football. Also, staying in Yankee-land it is easy to forget that a more elegant and cerebral bat-&-ball sport exists :). So strangely, Australia with their bouncer sized cricketers always gave me the satisfaction that yes, the game I love so much is indeed not anachronistic and irrelevant. The Aussies like cricket and love it too. Just like me. At the same time I disliked them for their almost total and sometime arrogant dominance in world cricket. That and the fact that Sir Don Bradman was an Aussie :). Lets hope that final 2 Test matches are more competitive!

---

Precisely when I was missing my best friend - my pet dog, I came across this:

"A dog is the only thing on earth that will love you more than he loves himself." ~ Josh Billings

I always wonder that although they are supposed to be the dumb ones unable to tell us how they feel, why is it I who is frequently at a loss of words with them?

---

I recently booked air tickets for visiting home this December. As I had a lot of constraints, I first thought of approaching a travel agent. That didn't work as the quotes I was getting were way too high. So, I finally decided to get myself in the mess that is online ticket reservations. I generally go to Orbitz as it is the best of the worst. It took me a frustrating 6 hours to get a reasonably priced ticket on that site. The most irritating part is that these websites on the first search advertise impossibly low fares and just as you decide to take it, they throw an innocuous error - 'Due to traveler demand, this flight is not available.' or 'The flight fare has been increased just now' - Yeah I believe you. Already tired, I found myself ready to accept any fare just to end the agony. The really intriguing part is that these misleading fares are still being shown! If this is not a blatant bait-and-switch strategy, what is! Other sites like Kayak etc. are worse. I do think these guys have to solve this thing (if they think this is a problem that is).

---

Another rant. This is against my amazing landlord. Just to give a taste of what my roommate and I have gone through:

• The apartment was not ready even 10 days into the lease, Reason: the landlord was too greedy to let the last tenant's lease end exactly when ours started. In fact, the apartment is still not ready - with things here and there left to be done.
  
• Within a week of entering the place, our apartment was burgled. Not sure what was taken fortunately, but the suitcase locks were broken. I still suspect the workers who had the keys. But our landlord decides to install a new lock and graciously gives a copy of them to these workers. Ohh by the way, these workers are now being searched for by the police for some theft.
  
• We didn't have hot water in the apartment for a good two weeks after that. Reason: the plumbing was faulty and the gas was leaking when it started.
  
• Next, our refrigerator started leaking like a water tap. Reason: it was an old one which should not have been there in the first place. Anyway, he took the ice out and we are patiently waiting for the next leak now.
  
• Next when the cold started, we found out that the heating was not working. Dutifully the landlord mouthed numerous "I'll do it" quotes. But it has not been fixed even now - a month on. Thankfully, after pestering him no end, we managed to get a couple of room heaters which at least make our rooms livable.
  

In spite of all this, the landlord is seemingly insensitive to our problems. And to add insult to injury, he calls us his 'buddies'. So, is it OK if one friend sues the other? :)

Update: The heating in our apartment has started. But as a result, the heating in the landlord's own place (which is just 2 floors below ours) stopped! He is busy dealing with that at present - I hope he doesn't screw up our heating now.

Joy of the Dawn

Rays tip-toe on my face
Cheating the blinds
Announcing their arrival
Tearing night's dark sheath

Life has begun - they proclaim!
Birds are serenading
Flower buds are bursting
Impregnating air with bliss

So spry; yet so calm
Dew-drops sit still
Yearning to fly unto Heaven
Or frolic with your eyes
Creating colors from white

My hapless soul glances outside
Allured by grass soft and wet
Summoned by fragrances I least understand
Is this a fortuitous accident?
Or a divine stratagem?

Clear skies embrace me
With the warmth of a Mother
And the passion of a Lover
Beauty justifying one's existence
Akin the Child's simple innocence

I try to resist the ephemeral
But isn't it Nature's elixir?
Have I drowned myself
Head over heels
In the Joy of the Dawn?

Nostos and Algos

Nostalgia as a word traces its etymological origins to (nostos) homecoming and (algos) pain. Interestingly, some computer scientists believe that the word 'algorithm' is derived from 'algos' as well! :)

Nostalgia is a strange thing. It was in fact first thought of as a medical condition. Some think of it as a vague, distant and alien emotion. Some romanticize it to such an extent that it nauseates you. My personal view (as for a vast majority of people I guess) is that it is a dirac function - mostly non-existent, but suddenly it comes and shoots up and then everything is normal again. And as you get older, it gets easier to drown in one of these bouts!

My most recent bout was when I saw two amazing photo sets one on India and one on my old school. Although it is too biased towards the current events in the country (more precisely in the Northern heartland), some photos are still breathtaking. Don't miss to check out the one with the majestic Royal Bengal Tiger! And the pictures from my school where I studied for 12 years evoke nothing but warm and fuzzy feelings and remind me of the time when my biggest worries were when I will go out and play and what would Mom make me for dinner!

Sometimes it is funny as how when you are in the present - I mean actually experiencing a situation - and think that you would eventually feel nostalgic about it! Sometimes even the bad memories can become a source of nostalgia. This is what I don't understand. Is this the case of the spectatorial axiom: distance automatically brings perspective? May be those situations weren't that bad after all? Or one is subconsciously trying to suppress the bad parts and trying to remember the good ones? Or as Franklin Adams once simply put, "Nothing is more responsible for the good old days than a bad memory"!

---

Have a meeting in < 2 hours (am I the only one to have Friday 4:30pm. meetings?), so later!

Update: The meeting was a short one thankfully - otherwise I was on the verge of stealing some winks! I guess having a DB group get-together immediately after helped :)

Dreams

Someone told me to dream
to dream free, big and bold!
then why am I scared?
of the possibilities that behold!

I was there though, happy
Looking ahead at the reverie
Or instead, was it the fancy
laughing back at me?

Thousand dreams there are
Which to choose? Which to destroy?
What if I fail? What if I blunder?
Hundred questions at such I flounder!

Time presses for an answer
Look around me, mine always say
Immersed minds, confident and positive
Swimming towards goals, without any delay

Made that way they are, probably
I hypothesize rather wildly
Cocooned from world I am, may be
Confused and random, thought seems hazy

Do others know what goes inside?
Reflecting the light like the moon
Like the Jester in pain
I laugh and behave more of the same

Hope hasn't deserted me yet
Some rays of glory fall on me
Is it the Dawn? The beginning of a new day?
I don't want to know, ignorant
I try to dream. And ask myself - which is the way?

Pamela's

Ok, on the demand of a blog reader, here's a 'lighter' post :) (Yeah, I better keep the anyway small number of readers happy!)

So, Pamela's is the name of this awesome restaurant chain in Pittsburgh. And I moved into an apartment just one-fourth of a block from one of the locations. Pamela's serves breakfast all day (I guess that makes it a diner or something?). And that breakfast has some of the best hotcakes, french toasts and what not.

Before this apartment, the only location of Pamela's which was easy enough for access was near CMU. Moreover, I had heard about the place a lot from all the friends here. Hence, I just had to make questionable excuses which would allow me to go to Pamela's. The place used to open at 7:30a.m. in the morning. Some 'plans' used to look like,

• On the eve before submission of a big assignment: 'Hey, lets waste our time playing foosball and monopoly till dinner. Then work and put a night-out (and screw our next whole day) and then have a fantastic breakfast at Pamela's in the morning!'
• On the India-Australia Cricket final match, even though we all had important meetings next day: 'Hey, lets watch the amazing cricket on our office computers and put a night-out (and get a warning for over-usage of bandwidth) and then have a scrumptious breakfast at Pamela's in the morning!'
• On a general work day: 'Hey, lets work normally, just sleep in Wean Hall on one of the public couches (and get a back-ache) and then have an awesome breakfast at Pamela's in the morning!'
• On a more mundane day: 'Hey, lets just roam outside Pamela's till it opens'

Strangely, all of these plans looked reasonable then! And yes, I have implemented each of them. (ok, may be not the last one!) :)

Pamela's has in fact caused much heart-burn! Once, I managed to convince two of my friends that the way to spend a perfectly nice Sunday morning was to stay hungry till 12:00p.m. and then go and have the Sunday brunch at Pamela's. The plan was made that we all meet near school at 11:45a.m. sharp and then take the bus to the place. As it happened, in between frantic phone calls, all of us messed up the synchronization and turned up slightly late, and we ended up wasting 2hours, hungry and angry, in front of the school waiting for the next bus to take us there. We finally got the next bus and reached at about 3:00p.m. Early evening and we three haven't eaten anything yet the whole day. Turns out, the restaurant was closed - as it was some holiday which we all managed to over-look! Hurt and dejected, we tried finding some other place. But only one place was still open - Subway. :) After all this, we finally ate at one place we all mutually kind of hated!

Another time, on my birthday in fact, after braving through 3 buses, I reached there only to find that I had no cash. They only accept cash, and sadly there was not a PNCBank ATM within a km. With my steely resolve, I managed to locate a sidey ATM and get the cash. And guess what, it was 5p.m. already - their closing time!

But in spite of all this, my enthusiasm for that place has not decreased - for the great food and easy atmosphere. And it is reasonably cheap. And it is a nice way to hang-out with friends on Sundays :)

So, if you ever happen to be in Pittsburgh, give me a call, and we can go to Pamela's together for that perfect breakfast :) Call me before 5p.m. though and have enough cash for both of us!

No Meat, Me Vegetarian!

My first non-trivial post and I start off with something which bothered me a month ago. I spent the summer at Sprint Research Labs at a pretty place in the Bay area called Burlingame where, in the words of my manager, 'rich white families live complete with their kids and dogs enjoying the summer Sunday barbecues'!

As it happened, my group of friends in the lab were all non-vegetarians and as a result I frequented a lot of basically no-veggie-on-menu restaurants. Now for someone who places a fair bit of importance on good food, this was a major change. Although Pittsburgh can't match good old India, it was still OK. I was surrounded by numerous Tam Brahms, Gujju Boys and Marwari bodybuilders. And all of these budding scientists are veggies. So, it can be said that I was nicely ensconced from the big bad world - I didn't have to put that much effort to eat vegetarian :)

Coming back to California, given that I suddenly felt responsible, each lunch/dinner became a long question-answer session in the restaurant; either with the waiter, if he/she was not sure then with the more important looking person and if even he/she was not sure, then with the manager. "Does it have lard?" "Hmm, looks good, No meat, I mean I am a vegetarian, so no meat" "Ahh, so fish works right?" "Ohh no no, no meat means no beef, no chicken, no pork and no fish as well!", "Does it have oyster oil? or maybe fish oil then?" "Is egg OK"? "Dude, do you eat anything at all?!" were par for the course. And having a lot of Chinese lab-mates didn't help! :) Then it started outside restaurants to pretty much anywhere I had any food. "These marshmallows look good, but seems like they contain gelatin - is it fine?" "What about Kosher Gelatin? Must be better no?" (In fact, the kosher one is worse for Hindus at least, as it is sometimes made from cow skin compared to pig bones for the standard gelatin!) "Okay, definitely Pectin should be fine then"!

I dutifully did this for a little more than a month - then when eating out became such a chore that I resolved to ask myself why exactly I am vegetarian and why I need to take so much care. Most of the Indians are simply raised that way - they are vegetarians, just as the Sun rises from the east! In my case as well, I just continued with my up-bringing and despised meat as second nature without really giving it much thought. As eating vegetarian was easy enough, I just continued with it! After the hassles in California, my idea was that I will try to answer my vegetarianism as far as possible by using only logical arguments. This is because cooked meat in general doesn't really gross me out unlike many other Indians. Sure, I would hate to sit in-front of people removing the shells and eating crabs 'fresh' from the cooking pot, but I don't have a problem with cooked dishes containing meat (except some sea-food which are frankly stink-bombs!). Also as I am a traditional Telugu/Kannada Brahmin, clearly not everything can be explained by hard logic. But still, I think it gives me reasonable room to answer myself in a reasonable way why I can't/can eat marshmallows! :)

Hinduism just does not allow beef consumption. The reason is that Hindus revere the Cow. She is a giver and symbolizes fertility, abundance and life. She eats grass and gives us milk. She helps the farmers to till the land. She is docile and hardworking. She acts as mode of transport. Even the cow-dung is useful for humans! I can't think of any other animal which is useful to the humans in such a way! It is in fact but natural that Hindus began to worship her. Now you don't go and eat the one you worship, right?

What about other meat products then? Chicken? Pork? As far as I know, Hinduism does not really say anything about these. I don't think that they are "prohibited" as beef is, for even Brahmins. I asked my parents as to why I can't eat these (fearing an angry response though! :) ). Surprisingly (although a little reluctantly), they had no problem in me eating meat, but still their parental advisory was not to. Upon more prodding my dad said that not consuming meat is a way of discipline. It is a way of showing that you can control your senses and allows you to live a more 'dharmic' (aka religious and righteous) life. Hence, we Brahmins should not eat meat.

Fair enough I thought. But the actual reason for me had to be more than this. Some would say, we should not kill animals. Note that surely our ancestors must have been eating meat. I guess after all, the earliest humans had to be hunters right? In fact, if we did not eat meat, then the human race would not have survived at all for organized agriculture to flourish! So, I don't think there is anything inherently 'in-human' in killing animals for food. But I do think that there is definitely something in-human to systematically do some kind of mass industrial 'production' of animals and bloat them to monstrous levels, all for the sole purpose of killing them for food! Isn't animal life something important? One would say don't the vegetarians kill plants then? Yes, but being humans, don't we have a hierarchy of living beings? Fellow homo sapiens are at the top, sentient beings who can convey us their pain are next and plants are after that. Clearly, that is why cannibalism is despised everywhere (well, almost!). Thus, according to me we have a greater responsibility towards animal life. Plants are important too, but as nature has told us to eat either plants or animals, eating plants is OK! Consequently, I felt that the modern meat production system is unnatural and it is fundamentally different than the natural instinct guiding the humans to kill animals in the wild. I abhor this and hence I do not eat meat.

What about stuff like gelatin etc? I think they fall under the same category as shoes and leather belts. These are primarily made from dead animals - basically animals are not killed for it (for the standard varieties I purchase anyway!). Hence, I decided it is fine to wear leather belts and eat products containing gelatin like marshmallows!

I agree I may have taken help from religion at some places, but at least now I have a better understanding of what makes me vegetarian. In any case, for lunch and dinners, food is not as important as whom you are there with! :)

Hello World

Is anybody out there?