Dodici Tazze di Caffè

Waiting for a Bus in Line?

2012-01-21T21:19:00.001-05:00

Problem:

At a certain bus stop at Port Authority Terminal in New York City, passengers wait for their bus in a line. A new bus arrives every hour and takes first, say, 40 people from the line to the destination, and rest have to wait for the next bus. However if there are less than 40 people in line, then there is a chance that you will get on the bus even if you are not standing in line. Assuming that all seat value equal, when is it profitable to stand in line?

-------------------------------------------------------------------

I had a simple solution to this problem: assuming that I arrive 30 mins before the bus, I wait 5 minutes and count how many people arrive within that time span to estimate the rate. If there are x people already in line, and people are coming at a rate of y persons per minute, then I stand in line if and only if x+30*y<40.
Unfortunately, I found out that this model is rather too simplistic, and we need to take care of a few more things here.

Many people wander around and only come to the bus stop when its time; so the rate of arrival is significantly higher in last ten minutes. This is a measurable anomaly!
Some of the passenger are ''pure statisticians'': they remember that they were able to get on the bus without standing in line in last 46 out of 50 times, and an expectation of >9/10 is good enough to convince them to enjoy their Mocha while relaxing on a bench.
And there are people who believe that God will save their seat no matter what; lets assume a ( dwindling?) constant number of them.
We should also consider that there are a couple of other crackpots doing the same math as we do, and have to cater for them too.

This should do it in most cases. But I can guess Game Theorists must have better models to solve this problem: where passengers are players, there is a cost associated with standing in line, and there is some unit profit for getting a seat(?? variable profit for different seats??) , and probably a cost of missing a bus. Decision may depend on the x (number of people already in line), time left in bus, rate of people arriving, and some randomness (lets assume that people are picked randomly if they are not waiting in line).

There is something counter-intuitive in nature here: assume that you are the fist person to arrive, then with very high probably you must decide not stand in line, and next person should also make the same choice, etc. and if no one stands in line then line will remain empty and it might happen that more 40 people are sitting and line in practically empty, then every seat is picked at random, which is chaotic and bus driver (mechanism?) does not like. Probably we can also add the information about the number of people sitting. I don't that makes problem interesting/boring/trivial.

Just babbling nonsense I guess, but any ideas, generalizations, models, then do share.

A Baker in Baghdad

2012-01-09T02:14:00.000-05:00

Once upon a time, there used to live a baker in Baghdad, who used to make the finest bread in town, and people used to come from far and wide to buy his bread. It was noticed that at times, some of his customers would pay him with fake coins; he would inspect the coin carefully for a few seconds, and then silently put it in his pocket, without saying a word. He never returned a coin to someone because it was fake.
When he was about to die, he made this nice dua to God, "you know very well man, that I used to provide people with freshly baked crunchy bread even for those fake coins, and they used to enjoy it. Now I am coming towards you with a fake Ibadat and actions; its not as you wanted it, but I beg that you accept it as I used to accept those fake coins because today I do not have original and real Ibadat and actions".

Views and opinions on various aside, poorly translated from Ashfaq Ahmed's, page 98 Zavia pt. 2: Hot Line!

He is dead, Jim!

2012-01-09T01:52:00.001-05:00

Just got my first "He's dead, Jim!" in Chrome...love you Google :D

A very old piece of love

2012-01-09T01:32:00.000-05:00

Piece is originally in Saraiki by Baba Ghulam Farid; I could not find the text or translation anywhere so errors and omissions are expected, bear with me!
While translating it, I felt like giving up half way through; it seems impossible to find equivalent words to translate his love that he so eloquently conveyed, I know I am very lousy at language but I suspect that its probably more because I have never loved anyone as much---let me correct myself: I am utterly incapable of loving as much :(
------------------------

Once, just once visit my place,
I will host you like its soul purpose of my life,

I will order all the flowers, and Misri, and Cardamom in the world,
I will have Rose perfumes ready for you after you are clean,
I will have Henna for you(??), and have Garlands,
I will seat you at the front, the place I made myself with soft mud.

I will have your hand in my hand all the time, even if you will fight over it,
I will massage you till mid night,
I want to have double as many days of such happiness,
when I can wake you up to make you eat some more.

I will have special Staffs for you from Shimla, and Turban from Jaipur,
Hundreds of Carnelians, blue and yellow Sapphires, and Diamonds,
Even though I am poor, my heart is rich:
whatever I will present to you, there will be nothing like it in universe!

==================================
Hik Waar Langh aa tu SaaDi jaah teiN
DariyaN karay saaN SikaaN laha kay

Phhul Aan Misri, LachaN mangay saaN,
Itrein Gulabein mulmul dhawasan,
Mihndi lawasein sehrein bandasain,
Aaggo milheisan bana bana kay,

hatela rakhsan, lar posein toray,
adhi raat taein daysan marooray
iyhay khusyan day dihein hoven dooray
jo shah khawesin nidroo utha ka

Shimla diyan sootiyan, ja pur day cheeray,
sah lal neelam pukraj heeray,
turay mein ghareeb, dil him ameer aay
jo shay mein dasain, dasain raja ka.

ہِک واری لنگھ آ توں ساڈی جاتے
داریاں کریساں سِکاں لیہا تے

Rumi Quote

2012-01-04T15:04:00.000-05:00

If once in this world I win a moment with you, I would trample both worlds under a dance of triumph.

I may change my mind later, but right now, at this moment, I think I have not heard a better line in this life so far :)

-PS These are, supposedly, taken from interpretation of James Cowan; I tried to find the original Farsi lines but I find it missing in a couple of books; may be I am looking up the wrong ghazzal or something. But who cares, right? Well, I usually do, because Farsi has an aura that is inexistent in translations normally, yet I can appreciate the thought in lines a lot.

They don't Care!!!

2011-12-27T23:41:00.001-05:00

Probably its because they have been treated in same brutal manner by their professors that they have decided to take the revenge on their students, or probably because they have been so submerged in their research that they have lost touch with the essential sense of humanity, I don't know the reason, but I have learnt the bitter unfortunate fact that most professors don't give a damn about grad students.

Ask them about their research, and they will take you on this fairy tale journey of how awesome and useful their work is. Follow it with you intention to do PhD in their field, and you will literally be able to observe changes in their face muscles. Most would ward you off, and ask you 'why don't graduate with an MS; you can land a much better job with that'. They think that its their duty to tell you not do a PhD; how miserable is that? Search up the title of this article on Google, and you will see how many crackpots have gleefully shared it on their blogs, as though they were doing a charity of sorts. You might think they are scared of losing their jobs so its kinda defense mechanism against future competition, but no, that feeling is only reserved for normal people; only conceivable reason for these nutts to do that is to hurt exciting energy filled new faces.

Now ask them for recommendation letters; so most professors would call you 'rude' since they don't know you enough and you asked them for a letter, and then they will forward you to following link (yep, they have made a blog for that purpose as well)

http://vlsi.cornell.edu/~rajit/recletters.html

Question remains in my mind, and the minds of my fellows, that why is it so crucial for them to consider a billion things before writing four sentences that could help someone get a freaking 12 week summer job? Would it kill their reputation so much if they say that someone was a good student of yours?

My objection is not on their response on a particular action; its about their behavior. Today they don't consider grad students as fellow human, actually its hard to tell if they consider anyone human, but they don't care if their remarks are going to ruin an other person's career; in fact my hunch is its not really going to make any difference to their behavior even if their student commits a suicide. They might be world class researchers, but unfortunately they are not good professors, they are not good humans :-(

Ashfaq Ahmed Quote

2011-12-24T01:30:00.002-05:00

Baba Jee once related his uncle's quote as below:

"Let people have better than they deserve, let them deceive you. If you will not fight with them, not argue with them, then they will tend to be peaceful. They will drop their weapons, they will be good and honest. And believe me son, humans want to be good and honest, they just don't get a chance to be. At least, you must give them this chance!"

And in an other episode of Zavia, he says,

"You don't have to give them food, or clothing or place or money. You just have to give them respect."

I like the use of word 'respect' in above sentence; no other word could have replaced it justifiably, not even 'love' :)

the Magic?

2011-12-19T22:27:00.000-05:00

Since beginning of my time, I have had this insane urge to witness some real magic or wizardry. When I was kid, I would listen intently to these stories being told by my grandma, by elders in neighborhood, and by friends at school. When I would get a chance, I would sit next to the most mysterious old-man at gatherings; I would walk through the least used paths in graveyards; I would wake up at 3 a.m. at night, sneak through the door and go sit in oldest religious places in the village. Usually, I would be scared to death on such adventures, but the crazy desire to see something anything supernatural always weighed more than the fear. Unfortunately, I was always disappointed...until now.

Unless you see it for yourself, I believe its supposed a mere story and a rather unbelievable one by definition, so I won't go into details; but I think I have witnessed a very powerful magic :)

The Love Song of J. Alfred Prufrock

2011-11-30T22:40:00.001-05:00

.
.
.
And I have known the arms already, known them all
Arms that are braceleted and white and bare
(But in the lamplight, downed with light brown hair!)
Is it perfume from a dress
That makes me so digress?
Arms that lie along a table, or wrap about a shawl.
And should I then presume? And how should I begin?
.
.
.
Shall I part my hair behind? Do I dare to eat a peach?
I shall wear white flannel trousers, and walk upon the beach.
I have heard the mermaids singing, each to each.
I do not think that they will sing to me.
.
.
.

T.S. Eliot (1888–1965). Prufrock and Other Observations. 1920.

lines from The Love Song of J. Alfred Prufrock

A Video Commentary on Someone Like You

2011-11-29T22:23:00.001-05:00

Apparently, Adele's song Someone Like You is a pop hit these days. GloZell did this superb video commentary on lyrics of this song; since the moment I listen to this, I wanted to share it. Following are the links to both videos on youtube.
WARNING: once you have watched both videos, you won't be really able to enjoy the original number, which I admit is paradisaical in itself, though little too sad for my taste...

On a side note, When I first listened to the line, "Never mind, I will find someone like you", I imagined she was being sarcastic and my thoughts immediately strolled back to Abida Parveen's classical urdu song "Dhoondo gay agar mulkoon mulkoon", which roughly translates to "You will wander all the lands on this earth, but you won't find someone like me---because there is no like me, you fool!".

Simpsons quote

2011-11-23T02:34:00.001-05:00

Mr. Burns: Bobo, I know I say this every century, but I'll never leave you behind again.

sigh!

Feynman on Philosophy of Science

2011-11-19T18:46:00.001-05:00

"Another most interesting change in the ideas and philosophy of science brought about by quantum mechanics is this: it is not possible to predict exactly what will happen in any circumstance. For example, it is possible to arrange an atom which is ready to emit light, and we can measure when it has emitted light by picking up a photon particle, which we shall describe shortly. We cannot, however, predict when it is going to emit the light or, with several atoms, which one is going to. You may say that this is because there are some internal “wheels” which we have not looked at closely enough. No, there are no internal wheels; nature, as we understand it today, behaves in such a way that it is fundamentally impossible to make a precise prediction of exactly what will happen in a given experiment. This is a horrible thing; in fact, philosophers have said before that one of the fundamental requisites of science is that whenever you set up the same conditions, the same thing must happen. This is simply not true, it is not a fundamental condition of science. The fact is that the same thing does not happen, that we can find only an average, statistically, as to what happens. Nevertheless, science has not completely collapsed. Philosophers, incidentally, say a great deal about what is absolutely necessary for science, and it is always, so far as one can see, rather naive, and probably wrong. For example, some philosopher or other said it is fundamental to the scientific effort that if an experiment is performed in, say, Stockholm, and then the same experiment is done in, say, Quito, the same results must occur. That is quite false. It is not necessary that science do that; it may be a fact of experience, but it is not necessary." Feynman, 1965.

In this house of thoughts and images: Rumi

2011-11-16T18:04:00.001-05:00

As they say, Rumi does not seize to amaze me. Follows original plus translation, a couple of lines are missing from this most beautiful recitation (first ode). Drop me a line, if you find any error in translation--my Farsi is, to put it bluntly, quite lousy.

من غلام قمرم غیر قمر هیچ مگو
I am a slave to the Moon;
Except about the Moon - say no more!
پیش من جز سخن شمع و شکر هیچ مگو
To me, speak of the light and sweetness and of nothing more!
سخن رنج مگو جز سخن گنج مگو
Don't speak of hardship, speak of nothing but treasures!
ور از این بیخبری رنج مبر هیچ مگو
they say you've lost touch, don't worry -- say no more!
دوش دیوانه شدم عشق مرا دید و بگفت
When I went insane; love saw me and called out:
آمدم نعره مزن جامه مدر هیچ مگو
Don't worry ! Here i come ! No need to scream or tear your garments! Say no more!
گفتم ای عشق من از چیز دگر میترسم
I told Love: look, I long for something else ...
گفت آن چیز دگر نیست دگر هیچ مگو
Love replied: there is no other thing anymore, fool -- say no more!
من به گوش تو سخنهای نهان خواهم گفت
I will whisper secret words in your ear
سر بجنبان که بلی جز که به سر هیچ مگو
Only nod your head to agree, utter no word, say no more!
قمری جان صفتی در ره دل پیدا شد
Following the path of the heart, the life-bestowing Moon appeared before me
در ره دل چه لطیف است سفر هیچ مگو
The journey is delicately pleasant, when you are on the path of the heart, say no more...
گفتم ای دل چه مهست این دل اشارت میکرد
I said to my heart "what kind of Moon are you ?" and it replied
که نه اندازه توست این بگذر هیچ مگو
You have no clue, just keep going and say no more!
گفتم این روی فرشتهست عجب یا بشر است
I asked "what wonder! Is this the face of an Angel or a human"?
گفت این غیر فرشتهست و بشر هیچ مگو
My Moonheart said "this is other than Angel or Man, say no more..."
گفتم این چیست بگو زیر و زبر خواهم شد
"What is it then? Pray tell! Or I will be uprooted and confused!" I begged
گفت میباش چنین زیر و زبر هیچ مگو
He replied "go ahead, be uprooted and confused, but say no more!"
ای نشسته تو در این خانه پرنقش و خیال
You who reside in this house of thoughts and images
خیز از این خانه برو رخت ببر هیچ مگو
Rise and leave it, begone, take your belongings, say no more!
گفتم ای دل پدری کن نه که این وصف خداست
I begged my Divine Heart: be paternal and kind to me, this is not how I expected Divinity to treat me!
گفت این هست ولی جان پدر هیچ مگو
He replied, "that is true but my dear son, say no more!" :)

KHANA DE KHAN PAROHNEY

2011-11-12T01:40:00.001-05:00

Thanks for reminding me, Amanat Chan :)

Connected Spaces

2011-11-12T01:27:00.001-05:00

Its charming but considerably incredible that the simple idea of connected spaces can all but enough to answer questions as threatening as below:

Q : Show that no two of following spaces are homeomorphic: R, R^2, [0,1],(0,1], [1,2]U[3,4]

Erdos–Ko–Rado theorem

2011-11-12T00:38:00.001-05:00

Q_0 : Let X=[n], what is the size of largest family F \subseteq 2^X, such that all f \in F are pairwise intersecting?

Answer : You can fix any element i \in X, and take all supersets, so certainly |F|>=2^{n-1}, and that |F|<=2^{n-1}, because of the symmetry in boolean algebra if you pick some set A to include in F, you must some one set X\A. So the half is best.

Q_1 : Let X=[n], what is the size of largest family F \subseteq (X \choose k), such that all f \in F are pairwise intersecting?

Answer: Again, you can fix one element, so |F|>=(n-1 \choose k-1), assuming n>=2k (other case is trivial). Proving that this is the best you can do, is the famous Erdos–Ko–Rado theorem. The case when k|n, is easy because you can use Baranyai's theorem to split the space into (n-1 \choose k-1) parallel classes, and you can pick at most one set from each class since they are non-intersecting.

Original proof by EKR uses this nice technique called Shifting. You start with an arbitrary family, and massage it towards left in boolean algebra while still preserving the property that it is pairwise intersecting i.e. shift operator S_ij for i < j, replaces j with i in each set of the family that contains unless the resulting set is already in the family. At the end you conclude that your shifted family can not contain element {n} in any of its sets.

Modest Views on Purposefulness of Life

2011-11-10T15:02:00.001-05:00

During a lunch conversation, a close friend expressed their rather modest views on purposefulness of life:

"I wish I could prove a theorem, write a book of fiction, make a girl happiest person on earth, teach history to school kids by hearth of a fire, create a poem, and then die calmly in my sleep---that or just have a dream in which I do all this shit and then die calmly in my sleep... :)"

I, on the other hand, just want a pair of thick woolen socks :)

CloudStream™ by Lufthansa

2011-11-06T03:48:00.000-05:00

Absolutely loved the concept, I can see it followed by every airline soon...

The Simpsons quote

2011-11-06T03:43:00.003-05:00

All right brain, you dont like me and I dont like you but lets just do this and then i can get back to killing you with the beer---Homer Simpson while taking final exam, he passed :)

Knitting Era

2011-11-05T07:03:00.000-04:00

Follow up on last post:

1) My grandfather had this sorta porch-cum-clubhouse back when I was a lad(4-5th grade?), and in hot summer days, it was always crowded with my aunts, and all other chatty girls from neighbors who would take turn on manual knitting and stitching jobs. I don't remember anything ever said in those sittings, but I do remember some of the amazing patterns involving Dihedral groups on flower petals, some characters, curves I remember it be quite peaceful 5-6 hours in the middle of the day, and there was no one to bother you, no cell phones, computers, TVs, radios, pretty much electronics free zone. I wonder where men used to be at that time of the day.

2) That was almost the end of that era, because I used to get a handknit sweater from my aunt. I think sometime around in my six grade, time became more precious to people, and I start getting market-bought sweaters. Motor wagons took over horse carts as they would take you to the city in 15 minutes compared to one hour on horse-carts; they turned out to be a cheaper solution too, so everyone was happy but I think we did lose something around that time. I would say much more, but at least we lost a culture...it might sound silly, but I wish I could promise my kids an hour long ride to school pulled by a smelly horse, an electronics-free summer where no one is forcing them to learn anything new, and they left to see the Pattern for themselves...

Knitting Patterns per se

2011-11-05T06:44:00.002-04:00

I bought a knitting kit, as a gift for a friend but as it was lying in my room for a week, I could not resist trying my own hands on it :)...apologies to my friends I guess

Patterns on wear-ables are recursive in general, so once your motor skills get used to it, its pretty smooth going from then on. But its rather difficult to actually perceive effects of individual stitch; since the process does not require this local comprehension, almost everyone skips to observe it. Why do we need to bring the yarn from over the needle? What happens if we alternate order of the needles every now and then (symmetrically)? Where to start with (number of rows/cols, tightness of stitch, relative width of different rows) to get some novel pattern? Map from a collection of simple stitches to the scarf/sock you get at the end maybe a total mystery to even those who have made thousands of them...makes process interesting :)

oh Captain, My Captain :)

2011-10-31T02:30:00.002-04:00

Revolution is evident, but I hope Pakistan doesn't turn into an other nameless prosperous country; I hope people remember that we do not stand for economy, or jobs, or happyness or healthcare; that Pakistan stands for an Idea, I pray that it remains that when all is said and done.

This is our Captain, and we, his underdogs....Imran hai, Imran hai, Imran hamara :)

http://www.nytimes.com/2011/10/31/world/asia/ex-cricket-star-imran-khan-leads-antigovernment-protest-in-pakistan.html

Quaternions are ON!

2011-10-31T02:03:00.000-04:00

I have always (almost always!) believed that the day I learn a new fact, is a day well spent and a day for which there is no \epsilon change in polyhedron of my knowledge is a total waste.

I was wondering that given these constraints, wouldn't it be the best strategy to live completely outside ones comfort zone, to meet people with whom you have absolutely no intersecting interests, read articles in a field you have utterly no idea about?
Of course, there are other constraints too, beside this one, and that they spare us from going on this venture, but lets assume otherwise for a sec; then is it really a good strategy? Or Would it make a life complete mess?

I learnt about Quaternions today; a friend had introduced me to them before but I didn't pay attention then I guess; looked at them from group theoretic perspective... today was not a total waste :)

The Balcony Scene

2011-09-23T23:52:00.000-04:00

love goes toward love as school boys from their books but love from love, toward school with heavy looks.

--romeo and juliet '96

Notes 21

2011-09-20T12:41:00.000-04:00

I note that you can tell how someone is feeling from the side of the road they are treading, in particular their energy levels. Measure of course is curving i.e. you want to note where they walk normally, and then on a given day, you can make an observation. An other example is the choice of seat from among a set that conveys some useful information as well. It is quite surprising how much some acute observers can infer with experience. Study probably falls under colorful umbrella of Reinforcement Learning, but lets confess that humans are, in general, pathetic at this science.

The One with my Regrets

2011-08-19T01:50:00.000-04:00

While one can never by completely happy with oneself, in general I believe given the circumstances, I have made fairly good choices in life; so there are no genuine regrets. But there are some distinguishable moments, that affected my thought process to a such remarkable extent that, to an unknowing observer would resemble a regret. I recall tiny two of them today.

1.
It was I think my 2nd or 3rd day in US, as I was enjoying a pleasant ride on my school bus on a beautiful sunny summer day. As I was trying to get off bus at my stop, being a gentleman, I gave way to this cute balck-hair girl sitting behind me to lead way. Right when she was at the door, she spun back, and staring bus driver in the eyes, enunciated in crystal clear voice "Thank you"!
I got off the bus, spotted a corner by the road, and there I sat and cried for at least half an hour. I had traveled four years in my college buses with the best drivers I have ever known, and in all those almost daily encounters over the span of four years, I had never spoken a word of Thank you to any of my drivers; I was devastated!

2.
At college, we had this friend who was notorious for borrowing money and not returning it. Once while I was working on a presentation with a couple of friends in my dorm, this guy peaked from the door and requested, each of us, one by one, for some money. Like others I asked to be excused as well because I didn't want to permanently lose 100 rupee.
On his way back, he bumped into my roommate, who could not say 'No' to him. He escorted him back to room, unlocked his closet, and handed him a bill of 100 rupee. He, like rest of us, did observe that this money would never return to his purse, but that moment I realized that more than 100 rupee was at stake that day. Over time I saw that roommate of mine make the most unlikely choices imaginable, but prints of this particular action of his would not be erased from my memory slate.

Simpsons quote

2011-08-15T20:24:00.000-04:00

When a man's biggest dreams include seconds on dessert, occasional snuggling and sleeping in til noon on weekends, no one man can destroy them---Simpsons

Before & After the deaths of our loved ones!

2011-08-15T01:06:00.000-04:00

A college friend of mine made it to the next level in an accident sometime ago, and I was browsing through group emails, wall entries on FB and everyone seemed so heart-wretched. Even people who hardly knew he existed in our class, people who woundn't even talk to him to relish some smug self-satisfaction, they all seemed so sad, even remembering how happy-go-lucky pal he was, and how his death was so cruel, and how he was lying in sweet gardens of heaven now, they know for sure! I couldn't help thinking that may be its just a product of some social constructs.

More recently, I wrote following for the obituary of a distant relative's death.."...What in the world, I wouldn't give to have just one more glimpse of her..." While I truly felt sorry while noting those lines, and yet now I feel rather more sorry to conclude that it was a lie. Imagine this situation that she is still alive but on her death bed, and wants to see me. So I receive this call while at my office that I have one chance of talking to her, and catching that "one last glimpse". Well, unfortunately I think I will really be hard pushed to leave a day's office work for this opportunity, and in all likelihood I would not go.
This, seemingly, is a contradictory behavior on my part because when she actually did die, I did sacrifice more than a couple of days at office, and I took the trouble to crawl outta my city and travel all the way to their place, and did feel sorry enough to write "What I would not give ...". Was I just following a non-optional social protocol or do sentiments really change when one has lost a chance? If they mean so much to us, why do we wait till their deaths to tell them how important they are to us?

I can see the faces of so many of my friends, I am never going to buy the discomfort to walk up to their doors to say 'Hi', and yet I have rather rehearsed what I am going to say on their respective passing away ceremonies. To that effect, I can also read the announcements of my own special little event on certain Yahoo groups, and the following sorrowful comments, and I dare expect a delightful little set of words even from people who as good as hate me today, or the people who wouldn't even so much as wave a hand or smile at me while passing by me in city today, even though their mischievous eyes did betray them and spot me.

It occurs to me that may be we have this unspoken social contract of sorts that we will say something good about or even go visit, each other once in a life time. I think a more humiliating thought did not occur to me today.
While shear size of the crowd at our funerals is quite precious to us, and we take genuine pride at this number like all men of honor, let us confess that most of us would rather trade those trips to our funerals, those convoluted words at obituaries, and even some tears at our graves then, for a riverside walk, a coffee at Bluebird and a big wide open smile NOW. But Can we allow the choice of delivery date to lie with the beneficiary in this contract? Its raining!

Once upon a Ramadan...

2011-08-11T08:22:00.000-04:00

Ramadan or Ramzan is this magical time in Islamic calender...oh google it for complete story:)

I once spent Ramadan as a paying guest with this cute couple (K&G Michaels) in a beautiful little hilly town in US, where I thought I was probably the only one fasting around. Anyway I tried to keep it a secret that I was fasting or sometime but it was to no avail because every other day I would find these sticky notes saying something like "How about supper tomorrow at 5?" (and yeah suppers/dinners are pretty early in the evening in US specially for couples); so some time by the end of first week of Ramadan, I ran out of excuses and it seemed pretty rude to plainly say 'no', so I told her...well it changed everything!

That evening when I went to kitchen to get something to eat, I found fridge with dozens of pots each with a note of my name on it...

"Black Pease salad- for Mudi",
"Cookies - for Mudi --note contains milk and butter", (making sure that it was Halal)
"Cucumber salad - for Mudi", (beliemme it was different)
"Apple Pie -for Mudi",
"Beans - for Mudi",
"Pizza - for Mudi (Don't worry, its vegan)"

They made sure that I would catch them eating...once Lia (her sister) offered me a cake, I shook my head politely but K looked so stoned as if she had raped me. They used to take me to these Tango lessons from this obsessed Superconductor Physicist (he would offer to me "Mudi you are good but boy it take two lifetimes to master Tango"), but now they would ask me "if I was feeling okay?", "if you had enuf energy". And she would so daintily walk me through her charming garden (Did you know they have different plants for Summer and Winter Squashes??)
She become so supper sweet, not that they were not sweet before but I would say, they added at least an other one and a half teaspoons of raw sugar :)

Oh I almost forgot to mention Faster and Monster (their awesome cats) who used to be my only company for Saheri, and they cuddle around my legs when I would stand up for Fajr...Miss them all :)

A touching commercial that rubs the deepest part of your heart.

2011-08-07T06:56:00.000-04:00

Facebook 'Friends'

2011-08-05T01:10:00.000-04:00

Once I was in trouble, like a real trouble, and in my misery, was wondering if some friend could help me out. I walked though names of close to 600 of my Facebook friends, and didn't think any of them was going to help me :(
Its not meant to say anything about my 'buddies', but this is how we are distorting definitions and characteristics of our, other wise, most-valued social bricks. I can not, literally, name a country from which I do not have a friend. So we are (or wanna get) connected to the whole world, and yet none of these connections is reliable enough, at times!

Luckily, for me, I did find a number on my phone book for the occasion, but I have learned over time that most of us do not have that luxury; we are lone souls wading through this 'miraculous' age of ours, bragging about how big our social circles are, and yet how lone, disconnected like a palm tree in Sahara we are - most unfortunate!

Developing static multithreaded debug libraries for CGAL

2011-07-28T01:59:00.000-04:00

Early this morning, I got following error while linking a project on windows that was using CGAL:

CGAL-vc100-mt-sgd.lib can not be found

While I finally fixed it but at time I was at complete loss, because building CGAL has gone quite successful, and it made no sense why this library should be missing.

Anyway, the problem is not with CGAL...it is with boost. So the easiest way to fix is:

1) remove all traces of CGAL and boost from your computer

2) install boost using windows installer (copying and building for the zip file on the site is much more tricky).

3) During installation, boost will give you options for building libraries, mutlithreaded, multithreaded with debug, static multithreaded, static multithreaded with debug etc. If you are confident which one u need, then go ahead otherwise select all of them.

4) Now build CGAL using normal cmake-gui.

5) you should have your required library in lib of CGAL...unless you are missing QT, which is needed for some of the libraries.

Similar errors for older Visual Studio versions and different modes of compilation may be as follows

CGAL-vc90-mt-sgd.lib can not be found
CGAL-vc80-mt-sgd.lib can not be found
CGAL-vc100-mt-s.lib can not be found
CGAL-vc90-mt-s.lib can not be found
CGAL-vc80-mt-s.lib can not be found

CGAL-vc100-mt-gd.lib can not be found

CGAL-vc90-mt-gd.lib can not be found

CGAL-vc80-mt-gd.lib can not be found

Linux build of CGAL relying on yum or apt-get goes much more smoother fortunately.

In a quite gloomy and gray city

2011-07-02T23:26:00.000-04:00

From Before Sunset:

I remember as a teenager I went to Warsaw, when it was still a strict communist regime..., something about being there was very interesting, I found. After a couple of weeks, something changed in me. The city was quite gloomy and gray...but, after a while, my brain seemed clearer. I was writing a lot more in my journal, ideas I never thought of before...
But, it took me a while to figure out why it felt, you know, so different. And then, one day, as I was walking through the Jewish cemetery, I don't know why, but it occurred to me there, I realized that I had spent the last 2 weeks away from most of my habits. TV was in a language I didn't understand, So, all I've been doing was...walk around, thinking right!

My brain felt like it was at rest, free from the consuming frenzy. And I have to say, it was almost like a natural high. I felt so peaceful inside,no... strange urge to be somewhere else, to shop...Maybe it could have seemed like boredom at first, but it quickly became very,very sore full. It's interesting, you know?

right now

2011-05-13T22:34:00.000-04:00

Right now I wish I could just sit with you: not kiss you, or hold you or run my fingers through your hair, not talk to you or laugh with you, not even look at your inescapable eyes; just sit next to you for one little eternity. Except for that I am the happiest soul beneath heavens, right now!

Invictus

2011-05-13T17:46:00.000-04:00

Out of the night that covers me,
Black as the pit from pole to pole,
I thank whatever gods may be
For my unconquerable soul.

In the fell clutch of circumstance
I have not winced nor cried aloud.
Under the bludgeonings of chance
My head is bloody, but unbowed.

Beyond this place of wrath and tears
Looms but the Horror of the shade,
And yet the menace of the years
Finds and shall find me unafraid.

It matters not how strait the gate,
How charged with punishments the scroll,
I am the master of my fate:
I am the captain of my soul.

- William Ernest Henley

Knowledge of a personality; a perspective

2011-05-09T21:39:00.000-04:00

Knowing a person or an entity isn't same as knowing their name, or meanings of their names or actions or attributes, or even habits. Its more like knowing their ''source code'' if you allow me to say so; that is knowing exact or partial feeling of how they are going to react to a certain situation. Its like you carry a part of them with you all the time. That probably leads to concept of ''missing someone'' that at times you can so vividly picture their response, you can imagine so perfectly their reaction, thought or gesture or even posture that you can almost evoke a life out of the moment; that vivid picture, along with the bitter realization that its not true is what feels like "missing". If you do not know someone, and if you doubt your cognizance of a character, unfortunately you can't predict a response and you can't possibly miss them. A knowing of an entity is supposed to take time, but sometimes an instance is enough; rest of the gap is engulfed by imagination but who cares; ignorance is bliss!
Did anyone study anything like that? any links?

Intersection of two convex polygons

2011-04-23T21:36:00.000-04:00

Here is a problem: you are two polygons (ordered list of their vertices), and you have to compute their intersection; you can assume that they are both convex and that they do have a positive intersection. I know there are known efficient algorithms for the problem, but right now I need to code it and won't mind a little bit a simplicity at cost of little bit extra time complexity as long as it remains practical for say a set of 1000 vertices. Here is my first algorithm: see if anyone can find an obvious counter-example to its correctness.

Let $A$ and $B$ be two convex polygons and we are looking for $A \cup B$
Obs1: vertices of $A \cup B$ are either vertices of $A$ or $B$ or intersection points of their sides. and O(n^2) we can find all such points and in O(n^2 log n) have them sorted in say x-axis. Lets call such sorted list as L.

Algo:

1. Calculate L.

2. Do a horizontal sweep, and events in this sweep are members of L. for each point check whether in lies in both $A$ and $B$ if not remove.

3. once done with step 2, take a convex hull of points left in L and return as the convex polygon $A \cup B$.

So the overall complexity is O(n^2 log n)????

Afterthoughts:

1. Step 1 should be doable in O(n) time as no side of polygon $A$ is going to intersect polygon $B$ more than twice as both are convex, also we never used sorting in our algo :)

2. Doing step 2 in O(n log n) seems bit tricky. But I think you can check for each point whether it lies in a polygon in at most O(log n) time, no?

So we have our O(n log n) algorithm, but in the name of simplicity let just workout O(n^2) algorithm for now :)

Where to find a solace today

2011-04-18T05:54:00.001-04:00

Mom of one of my college roommate has passed away. She was one of the nicest person I ever met. To me, its harshest of realities that I have been denied to ever meet her again in this life; its more than being deprived of a luxury or a right. Its like a part of my body has been cut off from me. Why I feel that way is inexplicable to me, as I only met her once. But today it sounds like, Why I only get to meet her just once. What would I not give for a touch of her hand on my hair and sweetest of a kiss on my forehead... But today I just get a scar on my heart; today I just get tears in my eyes, and a shinning reflection of her adorable face twinkling between those tears. We love you!

Subsequence with max Sum

2011-04-04T19:16:00.000-04:00

Let P be a sequence of n integers, problem is to find a subsequence S such that sum of s_i is maximized over all such S. Its obvious that if for all p_i >= 0 then P = S is the subsequence, also if all p_i < 0, then max(p_i) is such S. Now lets assume both these properties are not true. For solution below I assume that there is a positive infinity at the end of sequence, makes it bit simple.

Let max = - \infty
For i=1 to n do

while (p_i<=0) do
i++;
end while
temp = 0

LOOP:
while(p_i>=0) do
temp+=p_i
i++
end while

if(max
max=temp
end if

temp2=0

while(p_i<=0) do

temp2+=p_i

i++

end while

if(temp2

temp+=temp2

goto LOOP

end if

end For

return max
================================

I am least confident that this algorithm is going to work, but see if you can find any obvious problems. :)

A string manipulation site

2011-03-18T03:11:00.000-04:00

Ever you needed to do some niftly things to string but didn't feel like coding it? Found this nice site that does exactly that for you. Some of nice functions include:

Imagining a weird situation

2011-02-26T23:05:00.000-05:00

I just realized that for roughly all my life, I have not been in a situation when I didn't have money for food or something; in fact for last ten or twelve years or so I always had almost instant access to coins sufficient enough to get supplies for more than a month or so.
I wonder how would it feel to not have money to buy a dinner; how mind thinks in such a situation. As J.K. says Imagination is uniquely human capacity to envision that which is not; imagining nice weather, being at some beautiful place, proving Riemann hypothesis etc. But its really different.
I plan to try to simulate this situation one of these days. Did anyone try something like that? Experiences to share?

What to do with so much time?

2011-02-04T02:18:00.001-05:00

Okay I don't usually keep secrets, but here is one of my oldest; lets rip it. Earlier this morning I asked a friend if she was free to accompany us on a little trip this weekend, and response was typical, "No Mudassir, I am damn busy with this project, some other time maybe". I realize that there is a sufficient percentage of my friends who would so say to blow me away without me being able to figure it out but it has happened with some much frequency that it must be so. I was like, "Man what the hell is wrong with me?". Because I am never busy! Whenever someone asks me similar question, my thoughts are how much its gonna cost? how much effort is required? and who else is going? I almost never think time to be a constraint because I am always damn free. Its been always like that and it always scared me. When I was at college, I thought maybe everyone is free but they pretend otherwise but when I get a job then I will be busy: I will have so much to do, so many meetings, so many phone calls, emails to respond to that I will be able to say to others "sorry man I am busy" :).
Nope. I didn't happen. HR executive of a company that I worked with got even scared when I told her that I had 3-4hours totally free each working day. That didn't change even in grad school unfortunately where people don't even find time for a healthy stroll after a weeks hectic work.
Facebook has been the most effective remedy, I admit but still I enjoy 8-10 hrs sleep, follow cricket all around the world, watch movies, almost always cook my own food, regularly attend gym, work 6-8 hrs and still there is all the time in world to spare. Please shout that its same with you or I am gonna go crazy, oh boy.

From: http://mudasire.blogspot.com/

Neither the Veil Nor the Four Walls

2011-01-31T02:17:00.001-05:00

I heard of this upcoming film by Afia Nathaniel. I do believe that she has an exquisite story to tell here, but I also seriously wish she had not named or advertised it like that. I hope it is presented in different attire, but it sorta has been the same in almost all her work, and it kind of defines your audience among socio-political activists motivated by their own agenda, timekill-exhibition-goers, and probably a band of film award-voters. Unfortunately majority of the people this film is going to be about, are not going to watch it; not because it is, in some way, incomprehensible to them but because its mere title scares the hell outa 'm, not just scare, annoy or even anger them, so you don't target them at all and the result is going to be indifference, if not worse. Its like Mr. Bin Laden's messages to American people, not literally of course but almost same in spirit.

There is a frail Pakistani community that produces similar work, but one way or another they usually do take sides, and as a humble admirer of visual arts, I recognize it as storytelling gone Wrong. And that I dare say, because I see the Right at other places for example in Iranian cinema: exquisite works of Kiarustami doesn't need to present list of accolades it collected around the world to let you determine its quality, its meant for its people not for foreigners, and you always feel the message you are looking for even though it is never really pronounced to you. Like that.

From: http://mudasire.blogspot.com/

Proving the unTrue

2011-01-15T05:20:00.002-05:00

I spent last eighty hours trying to prove a lemma that turned out to be false in the end. There are quite a lot of statements in mathematics that community is 100-\epsilon % sure about that they are true and yet we do not have a proof for them(they have great list here). It seems a bit easy; well easy not the right word but probably one feels more confident while attacking such a problem because there is sound solid evidence that one can reach there with certain level of hardwork, dedication and a bit luck.

But its very tricky business working on something new, something you don't have much of an inclination or intuition whether its true or not. I remember once Mike suggesting that all you got to do is take a stand in such a situation, and that you must do.

Well, I took stand and attacked from several different cliffs I had in mind; it was an easy thing but every time I would miss to cover some little assumption that I needed to make; some "observation" that turned to be incorrect, it always eluded me and I finally lost faith. I looked for a counterexample and there she is sitting in front of me now.

Point is, if it is a bit harder problem and you keep your faith you may lose few precious years of your math life if you get unlucky;on the other hand, if you lose faith you lose the concentration/dedication to solve the problem in first place. You need to find a balance between faith and no-faith, if there is such a thing.

Salman Taseer episode

2011-01-04T13:16:00.002-05:00

Salman Taseer, a high profile politition, was gunned down by one of his own guards earlier today. There is a great deal of buzz on blogs, on social nets, groups etc., some happy at news of one less corrupt man in white collars, and others deeply resentful of his murder.

I can't party with anyone as I have followed any of this episode but this whole buzz sorta hurts me. Street people in Pakistan is absolutely no life surety as they leave their homes: killed a suicide attack, downed by frivolous looters, caught by agencies are just few ways they can be hit.

But as long as only powerful kills the powerless, there is a source and there is a sink and yours remain a civilized nation; chaos spawns when powerless also start killing powerfuls because then the balance is lost and you cease to have skill to contemplate who can kill who;sickness engenders. We are very sick people today :(

Snow Ice Cream

2010-12-26T17:00:00.002-05:00

For those who are greeting exceptionally harsh winter (specially my friends in West EU), I have a sorta consolation prize, that I discovered last year :)

Directions:

1. Collect a bowl full of CLEAN snow. If you can find a clean cut, when it starts to snow just place some big tupperware and check in 20-30 minutes later.

2. Add 1 tbs sugar, 1/2 tbs vanilla to roughly half a cup of milk, and mix it all.

3. Pour your mixture to half of the snow you collected and mix it, when done add the rest of the snow to give it a creamy look/taste. Enjoy at once.

It is one of the best treats of snow season; you gotta taste it to believe it, boy :)

P.S. : items in Step 2 are quite flexible to your taste; for example I would rather skip sugar and add 3tbs chocolate powder and some coffee; sometimes I sprinkle grounded almonds or pistachio too for little bit of crunch.

Pepper Deviled Eggs

2010-12-25T23:06:00.003-05:00

If you have time and access to kitchen, do try nice little cooking time with following. Recipe is available on various sites with little alterations; I took it from Foodnetwork. Happy holidays!

Ingredients

6 hard boiled eggs, cooled and peeled
1 teaspoon whole pink peppercorns, divided
1/2 teaspoon whole white peppercorns
1/2 teaspoon whole black peppercorns
1/2 teaspoon whole green peppercorns
1/2 teaspoon caper liquid
1/4 cup mayonnaise
1 teaspoon Dijon mustard
1/4 teaspoon kosher salt
Pinch sugar

Directions

Slice the eggs in half from top to bottom. Scoop the yolks into a medium mixing bowl and lay the whites aside. Place all of the peppercorns, except 1/2 teaspoon of the pink peppercorns, into a spice grinder and process until ground well. Add the ground peppers, caper liquid, mayonnaise, mustard, salt and sugar to the egg yolks and using a fork, stir to thoroughly combine. Place the mixture into a zip-top plastic bag and cut a small hole at one of the corners. Pipe the mixture into each of the white halves. Coarsely grind the remaining 1/2 teaspoon of pink peppercorns and use to garnish the top of each egg.

Chill for at least 1 hour in the refrigerator before serving.

HPDH Part 1

2010-12-24T22:10:00.002-05:00

After carefully watching reviews and ratings for more than a month now, I finally mustered up the courage to go and watch Deathly Hallows; after all how worse could they get after what they did before, and first time, for an HP movie, I walked the stairs to my seat with some expectations in mind, or heart perhaps. I am sorry, I am disappointed once more.

There were some improvements, though, in my view, specially in the acting performances of lead characters. Helena Bonham Carter did a fine job too with Bellatrix Lestrange. Unfortunately Alan Rickman is growing too old for Professor Snape, not at all appears as loathsome as he should; I don't know, can't they come up with a better makeup for him? Anyway, the main problem with the movie is it does not sound like a story, its just a bunch of events with almost no perceivable connection to link them plus some flashing lights to cover things up. Music has hit a new rock bottom too.

A fan of HP leaves with the feeling, messed-it-up-again-bro and muggles leave with what-the-hell-just-happened on their tongues. Fail.

Delaying Gratification

2010-12-24T17:05:00.003-05:00

Delayed gratification is very broad concept in modern psychology, and is defined as "sacrificing present comforts for future gains" but I (we, most of us?) was introduced to a more specific use of it by Scott Peck in Road Less Traveled, that is : to sort "todo list" in ascending order of comfort.
I found this to be a very handy principle, quite rare among advices that we gather from our Elders, in the sense that it is easy to understand and not so hard to follow either. Its not like, do the right thing, follow your heart, don't procrastinate etc.

For example you have just had dinner and you gonna watch some exciting movie but you know you also got to brush your teeth, to most a less pleasant act, its usually more profitable to have it done with early, like completing your homework before playing FiFA, or TeXing down the parts of proof as you have them rather than keeping them in head till conference deadlines.

I was wondering if there are plausible exceptions to this rule? Times when you can play now, pay later?

Interacting with R plots

2010-12-15T07:18:00.000-05:00

Found following extremely useful. From: http://www.stat.wisc.edu/~deepayan/SIBS2005/demos/base-graphics.html

Interacting with plots

Standard R graphics has rather minimal support for interaction, mainly through the functions locator() and identify(). (There are interfaces to external software with better interaction facilities.)

plot(x, y) ## left-click to select points, right-click to stop identify(x, y)  ## click on 5 points to make a polygon out of them polygon(locator(5))

Reason is ruthless; yet Love is even more, Purer, and nimbler, and more unafraid

2010-12-13T19:49:00.002-05:00

I must have posted this before but can't find so here it goes once more: Iqbal in Farsi!

در معنی حریت اسلامیہ و سر حادثۂ کربلا

ہر کہ پیمان با ہوالموجود بست
گردنش از بند ہر معبود رست
مؤمن از عشق است و عشق از مؤمنست
عشق را ناممکن ما ممکن است
عقل سفاک است و او سفاک تر
پاک تر چالاک تر بیباک تر
عقل در پیچاک اسباب و علل
عشق چوگان باز میدان عمل
عشق صید از زور بازو افکند
عقل مکار است و دامی میزند
عقل را سرمایہ از بیم و شک است
عشق را عزم و یقین لاینفک است
آن کند تعمیر تا ویران کند
این کند ویران کہ آبادان کند
عقل چون باد است ارزان در جہان
عشق کمیاب و بہای او گران
عقل محکم از اساس چون و چند
عشق عریان از لباس چون و چند
عقل می گوید کہ خود را پیش کن
عشق گوید امتحان خویش کن
عقل با غیر آشنا از اکتساب
عشق از فضل است و با خود در حساب
عقل گوید شاد شو آباد شو
عشق گوید بندہ شو آزاد شو
عشق را آرام جان حریت است
ناقہ اش را ساربان حریت است
آن شنیدستی کہ ہنگام نبرد
عشق با عقل ہوس پرور چہ کرد
آن امام عاشقان پور بتول
سرو آزادی ز بستان رسول
اللہ اللہ بای بسم اللہ پدر
معنی ذبح عظیم آمد پسر
بہر آن شہزادہ ی خیر الملل
دوش ختم المرسلین نعم الجمل
سرخ رو عشق غیور از خون او
شوخی این مصرع از مضمون او
در میان امت ان کیوان جناب
ہمچو حرف قل ہو اللہ در کتاب
موسی و فرعون و شبیر و یزید
این دو قوت از حیات آید پدید
زندہ حق از قوت شبیری است
باطل آخر داغ حسرت میری است
چون خلافت رشتہ از قرآن گسیخت
حریت را زہر اندر کام ریخت
خاست آن سر جلوہ ی خیرالامم
چون سحاب قبلہ باران در قدم
بر زمین کربلا بارید و رفت
لالہ در ویرانہ ہا کارید و رفت
تا قیامت قطع استبداد کرد
موج خون او چمن ایجاد کرد
بہر حق در خاک و خون غلتیدہ است
پس بنای لاالہ گردیدہ است
مدعایش سلطنت بودی اگر
خود نکردی با چنین سامان سفر
دشمنان چون ریگ صحرا لاتعد
دوستان او بہ یزدان ہم عدد
سر ابراہیم و اسمعیل بود
یعنی آن اجمال را تفصیل بود
عزم او چون کوہساران استوار
پایدار و تند سیر و کامگار
تیغ بہر عزت دین است و بس
مقصد او حفظ آئین است و بس
ماسوی اللہ را مسلمان بندہ نیست
پیش فرعونی سرش افکندہ نیست
خون او تفسیر این اسرار کرد
ملت خوابیدہ را بیدار کرد
تیغ لا چون از میان بیرون کشید
از رگ ارباب باطل خون کشید
نقش الا اللہ بر صحرا نوشت
سطر عنوان نجات ما نوشت
رمز قرآن از حسین آموختیم
ز آتش او شعلہ ہا اندوختیم
شوکت شام و فر بغداد رفت
سطوت غرناطہ ہم از یاد رفت
تار ما از زخمہ اش لرزان ہنوز
تازہ از تکبیر او ایمان ہنوز
ای صبا ای پیک دور افتادگان
اشک ما بر خاک پاک او رسان

Translation by Arthur John Arberry:

CONCERNING MUSLIM FREEDOM, AND THE SECRET OF THETRAGEDY OF KERBELA

Whoever maketh compact with the One
That is, hath been delivered from the yoke
Of every idol Unto love belongs
The true believer, and Love unto him
Love maketh all things possible to us
Reason is ruthless; Love is even more,
Purer, and nimbler, and more unafraid
Lost in the maze of cause and of effect
Is Reason; Love strikes boldly in the field
Of Action. Crafty Reason sets a snare;
Love overthrows the prey with strong right arm.
Reason is rich in fear and doubt; but Love
Has firm resolve, faith indissoluble.
Reason constructs, to make a wilderness;
Love lays wide waste, to build all up anew.
Reason is cheap, and plentiful as air;
Love is most scarce to find, and of great price.
Reason stands firm upon phenomena,
But Love is naked of material robes.
Reason says, Thrust thyself into the fore”
Love answers Try thy heart, and prove thyself
Reason by acquisition is informed
Of other; Love is born of inward grace
And makes account with Self. Reason declares
Be happy and be prosperous; Love replies
Become a servant, that thou mayest be free
Freedom brings full contentment to Love’s soul
Freedom, the driver of Love’s riding-beast
Hast thou not heard what things in time to war
Love wrought with lustful Reason? I would speak
Of that great leader of all men who love
Tuly the Lord, that upright cypress-tree
Of the Apostle’s garden, Ali’s son,51
Whose father led the sacrificial feast
That he might prove a mighty offering;52
And for that prince of the best race of men
The Last of the Apostles gave his back
To ride upon, a camel passing fair,53
Crimsoned his blood the cheek of jealous Love
(Which theme adorns my verse in beauty bold)
Who is sublime in our Community
As Say, the Lord is God exalts the Book.54
Moses and Pharaoh, Shabbir and Yazid-55
From Life spring these conflicting potencies
Truth lives in Shabbir’s strength; Untruth is that
Fierce, final anguish of regretful death.
And when the Caliphate first snapped its thread
Fron the Koran, in Freedom’s throat was poured
A fatal poison, like a rain-charged cloud
The effulgence of the best of peoples rose
Out of the West, to spill on Kerbela,
And in that soil, that desert was before,
Sowed, as he died, a field of tulip-blood.
There, till the Resurrection, tyranny
Was evermore cut off; a garden fair
Immortalizes where his lifeblood surged.
For Truth alone his blood dripped to the dust,
Wherefore he has become the edifice56
Of faith in God’s pure Unity. Indeed
Had his ambition been for earthly rule,
Not so provisioned would he have set forth
On his last journey, having enemies
Innumerable as the desert sands,
Equal his friends in number to God’s Name.
The mystery that was epitomized
In Abraham and Ishmael through his life
And death stood forth at last in full revealed.
Firm as a mountain-chain was his resolve,
Impetuous, unwavering to its goal
The Sword is for the glory of the Faith
And is unsheathed but to defend the Law.
The Muslim, servant unto God alone
Before no Pharaoh casteth down his head.
His blood interpreted these mysteries,
And waked our slumbering community.
He drew the sword There is none other God
And shed the blood of them that served the lie;
Inscribing in the wilderness save God
He wrote for all to read the exordium
Of our salvation. From Husain we learned
The riddle of the Book, and at his flame
Kindled our torches. Vanished now from ken
Damascus Might, the splendour of Baghdad,
Granada’s majesty, all lost to mind;
Yet still the srings he smote within our soul
Vibrate, still ever new our faith abides
In his Allahu Akbar, Gentle breeze,
Thou messenger of them that are afar,
Bear these my tears to lave his holy dust.

Crazy bidding on iPod

2010-10-19T21:01:00.001-04:00

From:http://blog.computationalcomplexity.org/2010/10/my-trip-to-denmark.html

At the workshop someone ran one of these weird rule auctions that on large scales is essentially a lottery. It costs 5 DKK (about US$1) for each bid. Each bid must be a multiple of 5 DKK. The player with the lowest unique bid pays that bid and gets an iPod Touch. I tried with a random bid. Game theorist Hervé Moulin won the auction. His strategy: Bid on every number from 5 to 75 DKK. A seemingly crazy strategy but with 15 DKK as his winning bid, he got the iPod for all of $18.

Drops of Oil on your Spoon

2010-10-16T04:05:00.003-04:00

I recount following from my favorite book by Paulo Coelho!

"A certain shopkeeper sent his son to learn about the secret of happiness from the wisest
man in the world. The lad wandered through the desert for forty days, and finally came
upon a beautiful castle, high atop a mountain. It was there that the wise man lived.
"Rather than finding a saintly man, though, our hero, on entering the main room of the
castle, saw a hive of activity: tradesmen came and went, people were conversing in the
corners, a small orchestra was playing soft music, and there was a table covered with
platters of the most delicious food in that part of the world. The wise man conversed with
everyone, and the boy had to wait for two hours before it was his turn to be given the
man's attention.
"The wise man listened attentively to the boy's explanation of why he had come, but told
him that he didn't have time just then to explain the secret of happiness. He suggested that
the boy look around the palace and return in two hours.
" 'Meanwhile, I want to ask you to do something,' said the wise man, handing the boy a
teaspoon that held two drops of oil. 'As you wander around, carry this spoon with you
without allowing the oil to spill.'
"The boy began climbing and descending the many stairways of the palace, keeping his
eyes fixed on the spoon. After two hours, he returned to the room where the wise man
was.
" 'Well,' asked the wise man, 'did you see the Persian tapestries that are hanging in my
dining hall? Did you see the garden that it took the master gardener ten years to create?
Did you notice the beautiful parchments in my library?'
"The boy was embarrassed, and confessed that he had observed nothing. His only
concern had been not to spill the oil that the wise man had entrusted to him.
" 'Then go back and observe the marvels of my world,' said the wise man. 'You cannot
trust a man if you don't know his house.'
"Relieved, the boy picked up the spoon and returned to his exploration of the palace, this
time observing all of the works of art on the ceilings and the walls. He saw the gardens,
the mountains all around him, the beauty of the flowers, and the taste with which
everything had been selected. Upon returning to the wise man, he related in detail
everything he had seen.
" 'But where are the drops of oil I entrusted to you?' asked the wise man.
"Looking down at the spoon he held, the boy saw that the oil was gone.
" 'Well, there is only one piece of advice I can give you,' said the wisest of wise men.
'The secret of happiness is to see all the marvels of the world, and never to forget the drops of oil on the spoon.' "

-The Alchemist

Nami Danum Kuja Raftum (I have no idea where am I going...)

2010-09-24T03:42:00.004-04:00

Found this great piece. Poetry is by Sufi Saint Hazrat Bu Ali Shah Qalandar and recited by Nusrat Fateh Ali Khan.

I put farsi lyrics below; started translating it but then I thought it was pretty lame compared to original thing...I can tell you if you particularly interesting in whats going on but you got to learn Farsi dude.

منم محو خیال او نمی دانم کجا رفتم

شدم غرق وصال او نمی دانم کجا رفتم

غلام روی او بودم اسیر موی او بودم

غبار کوی او بودم نمی دانم کجا رفتم

به آن ما آشنا گشتم ، ز جان و دل فنا گشتم

فنا گشتم فنا گشتم نمی دانم کجا رفتم

قلندر بوعلی هستم به نام دوست سر مستم

دل اندر عشق او بستم نمی دانم کجا رفتم

Mori Araj Suno, Rabba Sachayaa of |Faiz by Tina Sani

2010-07-08T00:29:00.003-04:00

Following aired on Coke Studio (s03e03) this sunday. While I love almost anything by Tina aunti since my early school days, I couldn't really enjoy it perhaps because I had listened to this poem before as read by Ahmed Shah Jee whose voice keep ringing in my ear as I listen this. I think Tina can give it one more go. But this Kalam by Faiz is very beautiful, although I believe there are a few minor mistake. Below I put corrected punjabi lyrics. Enjoy!

“ربا سچیا“

ربا سچیا تو آکھیا سی
جا او بندیا جگ دا شاہ ہیں توں
ساڈیاں نعمتاں تیریاں دولتاں نیں
ساڈا نائب تے عالیجاہ ہیں توں
ایس لارےتے ٹور کد پچھیا ای
کی ایس نمانے تے بیتیاں نیں
کدی سار وی لئی او رب سائیاں
تیرےشاہ نال جگ کی کیتیاں نیں
کِتے دھونس پولیس سرکار دی اے
کِتے دھاندلی مال پٹوار دی اے
اینویں ہڈاں وچ کلپے جان میری
جیویں پاہی وچ کونج کرلاوندی اے
چنگا شاہ بنایا ای رب سائیاں
پَولے کھاندیاں وارنہ آوندی اے

مینوں شاہی نئیں چاہیدی رب میرے
میں تے عزت دا ٹکر منگناں ہاں
مینوں تاہنگ نئیں محلاں ماڑیاں دی
میں تے جیویں دی نکر منگنا ہاں
میری منیں تے تیریاں میں مناں
تیری سونہہ جے اک وی گل موڑاں
جے ایہہ مانگ نئیں پجدی تیں ربا
فیر میں جاواں تے رب کوئی ہور لوڑاں

(فیض احمد فیض)

FOCS 2010 Accepted Papers

2010-07-02T01:04:00.002-04:00

FOCS'10 accepted abstracts are out. Abstracts are available here. Some of the papers are linked here.

Following seems very interesting to me at first glance; look forward for them:

Improved Bounds for Geometric Permutations

Authors: Natan Rubin, Haim Kaplan and Micha Sharir (Tel Aviv University)

Abstract: We show that the number of geometric permutations of an arbitrary collection of $n$ pairwise disjoint convex sets in $\reals^d$, for $d\geq 3$, is $O(n^{2d-3}\log n)$, improving Wenger's 20 years old bound of $O(n^{2d-2})$.

Estimating the longest increasing sequence in polylogarithmic time
Authors: Michael Saks, Rutgers University and C. Seshadhri, IBM Almaden

Abstract: Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Let $n$ denote the size of the array. Simple $O(n\log n)$ algorithms are known for this problem. What can a sublinear time algorithm achieve? We develop a polylogarithmic time randomized algorithm that for any constant $\delta > 0$, given $f$ outputs an estimate of the LIS that, with high probability, is accurate to within an additive $\delta n$. More precisely, the running time of the algorithm is $(\log n)^c (1/\delta)^{O(1/\delta)}$ where the exponent $c$ is independent of $\delta$. Previously, the best known polylogarithmic time algorithms could only achieve an additive $n/2$ approximation.
The LIS problem can be formulated as a dynamic program. Our overall approach seems very general, and might be applicable to approximating other dynamic programs.

The Monotone Complexity of k-Clique on Random Graphs
Author: Benjamin Rossman, MIT

Abstract: Understanding the average-case complexity of natural problems on natural distributions is an important challenge for complexity theory. In this paper we consider the average-case complexity of the $k$-\Clique{} problem (for fixed $k$) on monotone circuits. A natural class of distributions in this context are Erd\H{o}s-R\'enyi random graphs $G(n,p)$ at threshold functions $p(n) \in \Theta(n^{-2/(k-1)})$, for which $\Pr(G(n,p)$ contains a $k$-clique$)$ is bounded away from $0$ and $1$. Our main result is a lower bound of $\omega(n^{k/4})$ on the size of monotone circuits which solve $k$-\Clique{} (asymptotically almost surely) on $G(n,p)$ for two sufficiently far-apart threshold functions $p(n)$, such as $n^{-2/(k-1)}$ and $2n^{-2/(k-1)}$. This result complements a previous lower bound \cite{STOC08} of $\omega(n^{k/4})$ on the size of $\AC^0$ circuits which solve $k$-\Clique{} on $G(n,p)$ for a single threshold function $p(n)$. These two lower bounds---obtained by different techniques in the different settings of $\AC^0$ and monotone circuits---support an intuition that {\em random graphs at the threshold may be a source of hard instances for $k$-\Clique{} in general}. (Note that similar beliefs about random \textsc{SAT} are common in statistical physics.)
In addition, we show that $k/4$ in this lower bound is tight up to $o(k)$ by constructing monotone circuits of size $n^{k/4 + O(1)}$ which solve $k$-\Clique{} on $G(n,p)$ for all functions $p : \N \to [0,1]$ (monotonizing a construction of $\AC^0$ circuits due to Amano \cite{Amano09}). This moreover demonstrates a gap between the worst-case and average-case complexity of $k$-\Clique{} on monotone circuits, in light of an $\wt\Omega(n^k)$ worst-case lower bound due to Razborov \cite{Razborov85}.
One technical contribution of this paper is the introduction of a new variant of sunflowers called {\em $(p,q)$-sunflowers}, in which petals may overlap (but not too much on average). We prove a combinatorial theorem (along the lines of the Erd\H{o}s-Rado Sunflower Lemma \cite{ErdosRado60}) implying the existence of large $(p,q)$-sunflowers in any large enough uniform hypergraph. For many applications of sunflowers (especially in circuit lower bounds), the use of $(p,q)$-sunflowers may give better parameters, as this paper shows.

Stability yields a PTAS for k-Median and k-Means Clustering
Authors: Pranjal Awasthi and Avrim Blum and Or Sheffet, Carnegie Mellon University

Abstract: We consider $k$-median clustering in finite metric spaces and $k$-means clustering in Euclidean spaces, in the setting where $k$ is part of the input (not a constant). For the $k$-means problem, Ostrovsky et al.~\cite{Ostrovsky06} show that if the input satisfies the condition that the optimal $(k-1)$-means clustering is more expensive than the optimal $k$-means clustering by a factor of $\max\{100, 1/\alpha^2\}$, then one can achieve a $(1+f(\alpha))$-approximation to the $k$-means optimal in time polynomial in $n$ and $k$ by using a variant of Lloyd's algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the $(k-1)$-means optimal is more expensive than the $k$-means optimal by a factor $1+\alpha$ for {\em some} constant $\alpha>0$, we can obtain a PTAS. In particular, under this assumption, for any $\eps>0$ we can achieve a $(1+\eps)$-approximation to the $k$-means optimal in time polynomial in $n$ and $k$, and exponential in $1/\eps$ and $1/\alpha$. We thus decouple the strength of the assumption from the quality of the approximation ratio. We also give a PTAS for the $k$-median problem in finite metrics under the analogous assumption as well. For $k$-means, we in addition give a randomized algorithm with improved running time of $n^{O(1)}(k \log n)^{\poly(1/\epsilon,1/\alpha)}$.
We also use our technique to obtain a PTAS under the assumption considered by Balcan et al.~\cite{Balcan09} that all $(1+\alpha)$ approximations are $\delta$-close to a desired target clustering, when all target clusters have size greater than $2\delta n$. Both results are based on a new notion of clustering stability, that extends both the notions of~\cite{Ostrovsky06} and of~\cite{Balcan09}. No FPTAS for the $k$-median problem over such stable instances exists, unless $\P=\NP$. Thus our algorithm is in a sense best possible for such instances.

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
Authors: Alexandr Andoni (Princeton University & Center for Computational Intractability) Robert Krauthgamer (Weizmann Institute) Krzysztof Onak (Massachusetts Institute of Technology)

Abstract: We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor; specifically, for strings of length $n$ and every fixed $\eps>0$, it can compute a $(\log n)^{O(1/\eps)}$-approximation in $n^{1+\eps}$ time. This is an {\em exponential} improvement over the previously known factor, $2^{\tilde O(\sqrt{\log n})}$, with a comparable running time~\cite{OR-edit,AO-edit}. Previously, no efficient polylogarithmic approximation algorithm was known for any computational task involving edit distance (e.g., nearest neighbor search or sketching).
This result arises naturally in the study of a new \emph{asymmetric query} model. In this model, the input consists of two strings $x$ and $y$, and an algorithm can access $y$ in an unrestricted manner, while being charged for querying every symbol of $x$. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We also provide a nearly-matching lower bound on the number of queries.
Our lower bound is the first to expose we hardness of edit distance stemming from the input strings being ``repetitive'', which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance, which is edit distance on non-repetitive strings, i.e., permutations.

Collaboration with Paul Erdős

2010-06-16T07:47:00.005-04:00

One of my professor (I won't tell the name for the obvious reasons, but he is a well-known mathematician) is of the view that it wasn't such a great idea to work with Paul Erdos because in "most of the cases" he already had a solution in mind and he just needed someone to type and send it to some journal for him.

I am not very convinced of this view. While I think there might have some chances when Uncle Paul granted Erdos number 1 to some just for that particular reason, but just look at most of this club: Babai, Bollobás, Tóth, Hajnal, Pach, Kleitman, Elekes, Turán, Trotter, Tutte, Lovász, Sárközy, Füredi, Gyárfás, Szekeres, Szemerédi, Szegedy, Graham, Rényi etc.; these guys are top lot today in DM. Almost all of them went to produce greats results on there own.

I had to write this para because I recently realized that many grad students, when encounter a paper in which Erdos is one of the authors, usually assume (perhaps unintentionally) that Erdos might have been the guy with the main idea and everyone else just happened to be around him at that particular time; this is so very untrue for all I can suggest.

Embedding Spanning Subgraphs into Large Dense Graphs

2010-05-12T19:50:00.003-04:00

Asif Jamshed will be defending his PhD on "Embedding Spanning Subgraphs into Large Dense Graphs". It promises to be one of the most interesting dissertation of a Rutgers CS student in recent times. Please do attend if you find time. Here are the details.

Date: 05/21/2010
Location: CoRE A (Room 301)
Time: 03:00 pm

Embedding Spanning Subgraphs into Large Dense Graphs

Asif Jamshed
Rutgers Univeristy

Defense Committee: Endre Szemeredi (Chair), Michael Grigoriadis, William Steiger and James Abello (DIMACS, Rutgers University)

The full announcement is attached in HTML format

PhD Defense

5/21/2010 03:00 pm

CoRE A (Room 301)

Embedding Spanning Subgraphs into Large Dense Graphs

Asif Jamshed, Rutgers Univeristy

Defense Committee: Endre Szemeredi (Chair), Michael Grigoriadis, William Steiger and James Abello (DIMACS, Rutgers University)

Abstract

Spanning Trees:

Bollobas conjectured that if G is a graph on n vertices, minDeg(G) >= (1/2 + \epsilon) n for some \epsilon > 0, and T is a bounded degree tree on n vertices, then T is a subgraph of G. The Problem was solved in the affirmative by Komlos, Sarkozy and Szemeredi for large graphs. They then strengthened their result, and showed that the maximum degree of T need not be bounded: there exists a constant c such that T is a subgraph of G if maxDeg(T) <= cn / log n, minDeg(G) >= (1/2 + \epsilon) n and n is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree n/2 + C \log n, where C is a constant depending on the maximum degree of T. Here we show that in general n/2 + O(maxDeg(T) x log n) is sufficient for every maxDeg(T) <= cn / log n. We also show that this bound is tight for the two extreme values of m i.e. when m = C and when m = cn / log n.

Powers of Hamiltonian Cycles:

In 1962 Posa conjectured that if minDeg(G) >= (2/3)n then G contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if minDeg(G) >= ((k-1)/k))n then G contains the (k-1)th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Komlos, Sarkozy and Szemeredi for large graphs using the Regularity Lemma. We present a "deregularised" proof of the Posa-Seymour conjecture which results in a much lower threshold value for n, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for n to around 100 at which point we will be able to verify the conjecture for every n.

We will also talk about other embedding problems in graphs.

Online Latex Editor

2010-05-10T23:43:00.002-04:00

For quite sometime now, I have been looking for a good online latex editor. While I have stumbled upon a few I didn't enjoy anyone enough to use it frequently. I think my search is over now.

Latexlab.org is an open source implementation of a web based LaTeX editor that provides a very user friendly interface to type, compile and view results etc. for your latex documents. Furthermore it is integrated into your GoogleDocs. Enjoy!

A counter-example to the Hirsch conjecture

2010-05-10T23:20:00.004-04:00

Gil Kalai reported earlier today on his blog following title and abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” by Francisco Santos:

Title: “A counter-example to the Hirsch conjecture”

Author: Francisco Santos, Universidad de Cantabria

Abstract: I have been in Seattle only once, in November 2003, when I visited to give a seminar talk at U of W. Victor Klee was already retired (he was 78 at that time), but he came to the department. We had a nice conversation during which he asked “Why don’t you try to disprove the Hirsch Conjecture”? Although I have later found out that he asked the same to many people, including all his students, the question and the way it was posed made me feel special at that time.

This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the d-step theorem of Klee and Walkup.

Hirsch conjecture is long standing open question that asks the truth of the statement "states that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameterno more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d."

Congratulations Santos. It is really an Oh-My-God news for most of us and for some it may be shocking too as a guy from Stanford commented "That’s my whole PhD work going to trash!"...I hope he was kidding!

Conference celebrating Endre Szemerédi's 70th birthday

2010-05-10T18:51:00.002-04:00

There is going to be a conference celebrating Endre Szemerédi's 70th birthday. There is hardly any area in Discrete Maths and TCS that has not benefited from Professor Szemerédi's work.

Conference is going to be in Budapest in early August. More details on

http://www.renyi.hu/conferences/sze70/

p.s.: look at that blistering list of invited speakers; perhaps I have never seen this many great mathematicians in one conference except perhaps for ICMs :)

One moment

2010-04-29T13:01:00.002-04:00

At one moment life is fantastic, you are enjoying every luxury you want. Everything is going so smoothly; classes are going good, you have dozens of different brilliant ideas for your research, you are in good financial standing. Social life is great; weather is sunny.

And the very next moment, it all sucks; you remember that you forgot to submit that high weighted HW, your research idea is rebuffed by your adviser, your boss calls you to inform "I am sorry but I don't think I have the authority to write you that letter that I gave you yesterday; I will take it back"; clouds appear from no where to intercept all your sunshine, and you realize you forgot your keys inside your office and will wade through the snow storm in t-shirt. Dementors suck the life out of every single object around you and you are left sinking in darkness of disappointment.

World is quantum my friends, I assure you!

The End of Muthu's class

2010-04-22T10:41:00.003-04:00

We just received an email that next Monday would be our last class for cs-514; I feel strangely sad about it but then I have always felt like that at the end of Muthu's classes. Its not really true about any of the other classes I have taken with other people. I don't think I learned a great deal in this term nor did I do so well on my "exam", but there is a magic in his class which kinda spellbinds you and it doesn't feel like a class. Its more like a family sitting down for/after dinner to discuss some real world problems. It was always like that even when we were 40 people jammed in for cs-513. I realize that I am emotionally weaker than most but I still guess that everyone feels little bit of it. Thank you Muthu; thank you everyone!

Abstracts in Papers of Medical Journals

2010-04-18T02:31:00.003-04:00

While skimming through some research literature in medical field (my roommate is grad student in Epidemiology at UMDNJ), I noticed they have a very interesting and organized way of putting the abstracts. here is what a typical abstract for an article published in JAMA looks like

Background: one line description of the background of the paper.

Design: is two lines of the methods, data sources, tools they used for the research work.

Results: is 3-4 sentences describing results. Results are mostly in numbers. e.g. 80% of the subjects expired prematurely.

Conclusion: Does not contain any figure, and is just a vague statement that can provoke possible future work.

Following page describes this outline more formally. I was wondering whether this 'system' can work in math and engineering journals where we have varying types/sizes of abstracts.

Too Karimi Man Kamina Barda Am

2010-02-20T06:29:00.000-05:00

Too Karimi Man Kamina Barda Am

(Hazrat Maulana Jalaluddin Rumi R.A)

Too Karimi Mun Kamina Barda Um
Laikin Az Lutf E Shuma Parwarda Um

Zindagi Aamad Bara'ay Bandagi
Zindagi Be Bandagi Sharmindagi

Yaad E Oo Sarmaya E Eeman Bo'ad
Har Gada Az Yaad E Oo Sultan Bo'ad

Sayyad O Sarwar Mohammad Noor E Jaan
Mehtar O Behtar Shafi E Mujrimaan

Choon Muhammad Pak E Shud Az Nar O Dood
Her Kaja Roo Karad Wajhullah Bood

Shahbaaz Lamakani Jaan E Oo
Rehmatal Lil Aalameen Dar Shaan E Oo

Mehtareen O Behtareen E Ambiyaah
Juz Muhammad Naist Dar Arz O Samaa

Aan Mohammad Hamid O Mahmoud Shud
Shakal E Abid, Sorat E Ma'bood Shud

Auliyah Allah O Allah Auliyah
Yani Deed E Peer Deed E Kibriyah

Her Ka Peer O Zaat Haqra Aik Na Deed
Nai Mureed O Nai Mureed O Nai Mureed

Maulvi Hargiz Na Shud Maula E Rum
Ta Ghulaam E Shams Tabraizi Na Shud

Translation:

You are the gracious and I am the ignoble, standing at your door.
You are my cherisher.

Life is only for devotion.
Life without devotion (worship or total submission) is disgrace.

Remembrance of him is the foundation of faith.
The beggars are like kings due to his rememberance.

Mohammad (pbuh) was purified of worldly things,
he got this reward:
God said to him, Whatever direction you face your prayer,
My face is to that direction.
His soul like an eagle of Heaven as God called him Mercy for all the creations of God.

There is no greater or better of all the prophets than Mohammad (pbuh).
He is the praise of God and therefore has been praised very much.
He is the reflection of God in the shape of a worshipper of God.

The friends of God are like God because God is their friend and in this way he who has seen his spiritual leader, sees God.
one who doesn't see his spiritual leader as God is not a true spiritual disciple.

Maulvi** could never be Maula-i-Rum*** if he had not devoted himself to Shams Tabrizi****

There is no greater or better of all the prophets than Mohammad (S.A.W)*.

* SallaAllah-u-Alaih-e-Wasslam (Peace be upon him)
** Maulana Rumi, who was called Maulvi because he was just a simple religious leader
*** to be recognized as spiritual leader or Master
****The spiritual Master of Maulana Rumi (Rehmatullah-e-Alayeh)

Typos may earn Google $500m a year - tech - 17 February 2010 - New Scientist

2010-02-19T23:46:00.000-05:00

"Google may be earning an alleged $500 million a year via companies and individuals who register deceptive website addresses.

The claim centres on a controversial scheme known as 'typosquatting', the practice of registering a misspelled variant of a popular web domain. For example, a typosquatter might register 'newscientsist.com' in the hope of getting visits from people who meant to type 'newscientist.com'.

If that mistake is made frequently enough, the owner of newscientsist.com can profit by placing ads on their page. They could, in particular, use Google's advertising network which automatically assigns ads to a page based on its content, or using keywords provided by the page's owner."...More on

Typos may earn Google $500m a year - tech - 17 February 2010 - New Scientist:

UK calls in Israeli ambassador over Dubai Hamas murder

2010-02-18T06:58:00.002-05:00

Goto New York Times, Washington Post, Fox news, MSNBC etc. and you will find absolutely no mention of it. True they are your allies but don't you feel any shame cheating your sworn responsibility to truth as journalists? What would people believe of you?

I do not even know why they are trying to hide it from their people.

http://news.bbc.co.uk/2/hi/middle_east/8521246.stm

Part 1: Whats wrong with America?

2010-02-08T15:48:00.001-05:00

Nope. This isn't one of those politically motivated lectures you find around all these days. Its just a small list of simple things that I have some difficulty standing here, and no american seems to be talking about them. I think some of them are much better handled in Eastern countries, so I would take the liberty to compare it with situation in Pakistan whenever relevant below. Please don't take this as an attack of smugness or something; I do acknowledge the fact that America is a great place to live in and life here is much easier than most parts of the world. I think it can be better.

Telecommunication:

One of first things I needed, when I landed here in US, was a phone service. I remember I was talking to this lady from AT&T, "what kind of connection do you want?", and I said something like "The simplest and cheapest one for now. My parents want to call me and I just want to be able receive their calls. I don't need to make any calls or data or anything...how much would it cost?". And she said "you will have to pay around 40$ per month. You will keep it for at least two years". You can imagine look on my face if you are from Pakistan/India. I talked to Verizon, Sprint, T-mobile etc guys but that was roughly the cheapest I could get.

I think that is huge amount to pay for your phone for a poor man at a time when governments around the world are striving to make forms of communication almost free. For example in Pakistan, you get to receive unlimited calls for six months by just paying 10 PKR (that is 12 cents for six months) And another 6 cents for sending unlimited SMS per month. And there is no contract attached to any of this; so keep it as long as you want and then throw it away. Sure there are packages for you if your pocket is heavy; with unlimited calls, 3G, GPS, television, it may cost you well over 50-60 bucks per month. But basic phone functionality of making/receiving calls/sms is well under control of almost everyone. Internet/TV/Cable charges have similar story.

Health:

Okay it does really fall under the description as everyone is talking about it but I guess I would still mention it for the fun of it :)

Last summer I got hit by my surfboard while on the beach and I was bleeding badly. I needed medical attention immediately but here is what happened.

As it happened to be a weekend, medical facility was only open for emergencies. I gave them a call and convinced them that it was an emergency enough; after some inquiry and identification procedure (my health policy etc.) I was allowed. I went there, after 15 minutes nurse checked me; my temperature, then my blood pressure, then medical history etc etc. It took 15 more minutes for her to complete form on computer. I was said to wait more. After more than one hour I was attended by a physician as there happened to be only one there at that time; she was kind and nice, and she prescribed few things that stopped bleeding and started recovery of wound. Thank you very much. But I don't think it was a pleasing experience overall.

Once in Lahore (a city in Pakistan) we were playing football (soccer I mean) at around mid night (ah my college days). A friend of mine got somehow a piece of glass stuck into his foot and it started bleeding.

We took him to nearest hospital, without any delay, he was attended by a doctor who gave him pills for the pain, removed the glass, bandaged his foot, and put for him in a bag medicine for recovery. Believe it or not, it all happened within 15 minutes, and it cost us nothing including medicine. Yes, and it was around 1 a.m. at night. Sure the facilities are not clean, sure beds in hospitals are old and weary, sure they don't have enough equipment to cure people, and of course they are not as qualified as an American doctor. But when you are struggling between life and death, they won't ask you if you have a health policy or not, they won't even charge you for emergencies, and they specially won't ask you for medical history while you are peeping blood because they don't have this many forms to fill on their computer screens; many of them don't even have computer screens :). As I said facilities are not great, but whatever they are, they are free and accessible to anyone there.

to be continued...

جب شعر سفر کرجائےگا

2010-01-23T20:47:00.003-05:00

By Wussat-ul-llah khan. Aug 26, 2008. src:http://www.bbc.co.uk/urdu/pakistan/story/2008/08/080826_faraz_gone_rza.shtml

ناصر کاظمی، احمد ندیم قاسمی، جون ایلیا، خاطر، قتیل، فارغ، منیر نیازی ، احمد شاہ فراز۔آسمانِ سخن کی یہ ڈار کل پوری طرح بکھرگئی ۔ظفر اقبال اور انور شعور نامی دو بچھڑی کونجیں پر سمیٹے بیٹھی ہیں۔اور اب ہم فرحت عباس شاہ، وصی شاہ اور سعد اللہ شاہ وغیرہ کے رحم و کرم پر ہیں۔

احمد فراز قبیلہ فیض کے آخری سورما تھے ۔یہ قبیلہ دنیائے ادب میں مزاحمتی نوالے کو معشوقی کے شہد میں ڈبو کر تناول کرنے کے لئے جانا جاتا تھا۔

احمد شاہ فراز اور انکے ہم عصروں میں ایک بنیادی فرق یہ ہے کہ اردو فراز کی سیکنڈ لینگیویج بھی نہیں تھی۔بلکہ اردو انہوں نے صحیح معنوں میں اپنی ریڈیو پاکستان کی نوکری کے زمانے میں سیکھنی شروع کی۔پھر تو وہ جانِ حیا ایسا کھلا ایسا کھلا کہ اہلِ اردو کے لئے تیرہ شعری مجموعے چھوڑ کر رخصت ہوا۔

ایک فراز وہ تھا جو

وہ بھی کیا دن تھے جب فراز اس سے
عشق کم، عاشقی زیادہ تھی

ٹائپ کی شاعری کررہا تھا اور پھر یوں لگا جیسے اس نے تخلیقی انجن پر پانچواں گئیر ٹربو کے ساتھ لگا دیا۔

تیرے بغیر بھی تو غنیمت ہے زندگی
خود کو گنوا کے کون تیری جستجو کرے
چپ چاپ اپنی آگ میں جلتے رہو فراز
دنیا تو عرضِ حال سے بے آبرو کرے

ہر ایک بات نہ کیوں زہر سی ہماری لگے
کہ ہم کو دستِ زمانہ سے زخم کاری لگے

یاد آیا تھا بچھڑنا تیرا
پھر نہیں یاد کہ کیا یاد آیا

اتنا بے صرفہ نہ جائے میرے گھر کا جلنا
چشمِ گریہ نہ سہی چشمِ تماشائی دے

یوں پھر رھا ہے کانچ کا پیکر لئے ہوئے
غافل کو یہ گماں ہے کہ پتھر نہ آئے گا

یارو مجھے مصلوب کرو تم کہ مرے بعد
شاید کہ تمہارا قدوقامت نکل آئے

رفتہ رفتہ یہی زنداں میں بدل جاتے ہیں
اب کسی شہر کی بنیاد نہ ڈالی جائے

کیا لوگ تھے کہ جان سے بڑھ کر عزیز تھے
اب دل سے محو نام بھی اکثر کے ہوگئے

میرے سخن کا قرینہ ڈبو گیا مجھ کو
کہ جس کو حال سنایا اسے فسانہ لگا

میری ضرورتوں سے زیادہ کرم نہ کر
ایسا سلوک کر کہ میرے حسبِ حال ہو

کیا مالِ غنیم تھا میرا شہر
کیوں لشکریوں میں بٹ گیا ہے

دانے کی ہوس لا نہ سکی دام میں مجھ کو
یہ میری خطا میرے شکاری نہیں بھولے

میری گردن میں بانہیں ڈال دی ہیں
تم اپنے آپ سے اکتا گئے کیا

درِ زنداں سے پرے کون سے منظر ہوں گے
مجھ کو دیوار ہی دیوار دکھائی دی ہے۔

گویا فراز کے ہاں عاشق کے لئے بھی معیاری مال وافر تھا۔معشوق کے لئے بھی اور انقلابی کے لئے بھی۔ایسا نہیں ہے کہ فراز نرا شاعر تھا۔وہ دنیا دار بھی تھا اور اسکا شمار اردو کے معدودے چند خوشحال شاعروں میں ہوتا تھا۔لہذا فراز کے اس شعری دھوکے میں نہ آئیے گا کہ
فراز تو نے اسے مشکلوں میں ڈال دیا
زمانہ صاحبِ زر اور صرف شاعر تو

یہ شعر اسلام آباد کی بیورو کریٹک زندگی سے پہلے کا ہے۔
لیکن اس نے اپنی دنیا داری کو شعر میں خلط ملط نہیں ہونے دیا۔چنانچہ فراز کو جو بھی شخص جس سمت سے دیکھنا چاہے اسے وہ ویسا ہی دکھائی دے گا۔


	اس خط کا عکس جو فراز نے سرکاری اعزاز واپس کرتے ہوئے لکھا تھا

سڑک کے آدمی کے لئے وہ براستہ مہدی حسن رنجش ہی سہی والا شاعر ہے۔اور کچی رومانویت میں لپٹے ہوئی نوجوان روح کے لئے وہ

کہا تھا کس نے اسے حالِ دل سنانے جا
فراز اور وھاں آبرو گنوانے جا

والا بال بکھیرو سخنور ہے۔

لیکن میرا فراز وہ ہے جس نے جنرل ضیا الحق کی تپتی آمریت کا سورج سوا نیزے پر ہوتے ہوئے کراچی کے ڈاؤ میڈیکل کالج میں نظم محاصرہ پڑھی تھی

میرے غنیم نے مجھ کو پیام بھیجا ہے
کہ حلقہ زن ہیں میرے گرد لشکری اس کے
فصیلِ شہر کے ہر برج ، ہر منارے پر
کماں بدست ستادہ ہے عسکری اس کے
وہ برق لہر بجھا دی گئی ہے جس کی تپش
وجودِ خاک میں آتش فشاں جگاتی تھی
بچھا دیا گیا بارود اس کے پانی میں
وہ جوئے آب جو میری گلی کو آتی تھی
سبھی دریدہ دھن اب بدن دریدہ ہوئے
سپردِ دارورسن سارے سر کشیدہ ہوئے
تمام صوفی و سالک، سبھی شیوخ و امام
امیدِ لطف پہ ایوانِ کج کلاہ میں ہیں
معززینِ عدالت حلف اٹھانے کو
مثالِ سائلِ مبرم نشستہ راہ میں ہیں
تم اہلِ حرف کے پندار کے ثناگر تھے
وہ آسمانِ ہنر کے نجوم سامنے ہیں
بس اس قدر تھا کہ دربار سے بلاوا تھا
گداگرانِ سخن کے ہجوم سامنے ہیں
قلندرانِ وفا کی اساس تو دیکھو
تمہارے ساتھ ہے کون، آس پاس تو دیکھو
سو شرط یہ ہے جو جاں کی امان چاہتے ہو
تو اپنے لوح و قلم قتل گاہ میں رکھ دو
وگرنہ اب کے نشانہ کمان داروں کا
بس ایک تم ہو، سو غیرت کو راہ میں رکھ دو
یہ شرط نامہ جو دیکھا تو ایلچی سے کہا
اسے خبر نہیں تاریخ کیا سکھاتی ہے
کہ رات جب کسی خورشید کو شہید کرے
تو صبح اک نیا سورج تراش لاتی ہے
سو یہ جواب ہے میرا ،میرے عدو کے لئے
کہ مجھ کو حرصِ کرم ہے نہ خوفِ خمیازہ
اسے ہے سطوتِ شمشیر پر گھمنڈ بہت
اسے شکوہ قلم کا نہیں ہے اندازہ
میرا قلم نہیں کردار اس محافظ کا
جو اپنے شہر کو محصور کرکے ناز کرے
میرا قلم نہیں کاسہ کسی سبک سر کا
جو غاصبوں کو قصیدوں سے سرفراز کرے
میرا قلم نہیں اوزار اس نقب زن کا
جو اپنے گھر کی ہی چھت میں شگاف ڈالتا ہے
میرا قلم نہیں اس دزدِ نیم شب کا رفیق
جو بے چراغ گھروں پر کمند اچھالتا ہے
میرا قلم نہیں تسبیح اس مبلغ کی
جو بندگی کا بھی ہر دم حساب رکھتا ہے
میرا قلم نہیں میزان ایسے عادل کی
جو اپنے چہرے پے دھرا نقاب رکھتا ہے
میرا قلم تو امانت ہے میرے لوگوں کی
میرا قلم تو عدالت میرے ضمیر کی ہے
اسی لئے تو جو لکھا تپاکِ جاں سے لکھا
جبیں پہ لوچ کماں کا، زبان تیر کی ہے
میں کٹ گروں کہ سلامت رہوں ، یقیں ہے مجھے
کہ یہ حصارِ ستم کوئی تو گرائے گا
تمام عمر کی ایذا نصیبیوں کی قسم
میرے قلم کا سفر رائیگاں نہ جائے گا

فراز محاصرہ پڑھ کر سٹیج سے اترے تو نعروں اور تالیوں نے چھت پھاڑ دی اور نوجوان انکے ہاتھوں کو پرنم آنکھوں سے اس طرح چومتے رہے کہ ایسی عقیدت فراز کے جدِ امجد کوھاٹ کے ولی حاجی بہادر کو بھی شاید میسرنہ آئی ہو۔

لیکن فراز نے جو کام جنرل ضیا کی آمریت کے ساتھ کر دکھایا ویسا کام جنرل مشرف کی آمریت میں نہ ہوسکا۔آدمی تھک بھی تو جاتا ہے نا ! لیکن عمر کے بوجھ سے آہستہ آہستہ دبنے والے فراز نے یہ ضرور کیا کہ جنرل مشرف حکومت کے ہاتھوں پانے والا نشانِ امتیاز دو برس رکھنے کے بعد اسی حکومت کے منہ پر مار دیا۔اس کے عوض کوئی سال بھر بعد احمد فراز کا سامان سرکاری کارندوں نے گھر سے اٹھا کر سڑک پر پھینک دیا۔

فراز سے میں نے آخری مصاحفہ گیارہ جون کو اعتزاز احسن کے لانگ مارچ سے قبل اسلام آباد پریس کلب میں کیا۔بوڑھے فراز کے چہرے پر وہی سرخی دوڑ رہی تھی جیسی سرخی برسوں پہلے جنرل ضیا کی آمریت کو للکارنے والے وجیہہ فراز کی آواز میں محسوس ہوتی تھی۔فراز نے پریس کانفرنس کے بعد بتایا آج کل وزیرستان پر ایک طویل نظم لکھ رھا ہوں۔جانے یہ نظم کب مکمل ہو۔۔۔۔۔۔۔

معلوم نہیں فراز کی یہ نظم کب سامنے آ ئے گی یا نہیں آئے گی۔تب تک برسوں پرانی اس نظم کے عکس میں آپ آج کے وزیرستان اور دیگر علاقوں کی تصویر دیکھ کر گذارہ کیجئے

تم اپنے عقیدوں کے نیزے ہر دل میں اتارے جاتے ہو
ہم لوگ محبت والے ہیں، تم خنجر کیوں لہراتے ہو
اس شہر میں نغمے بہنے دو، اس شہر میں ہم کو رہنے دو
ہم پالن ہار ہیں پھولوں کے، ہم خوشبو کے رکھوالے ہیں
تم کس کا لہو پینے آئے، ہم پیار سکھانے والے ہیں
اس شہر میں پھر کیا دیکھوگے، جب حرف یہاں مرجائےگا
جب تیغ سے لے کٹ جائے گی، جب شعر سفر کرجائےگا
جب قتل ہوا سب سازوں کا، جب کال پڑا آوازوں کا
جب شہر کھنڈر بن جائے گا، پھر کس پر سنگ اٹھاؤ گے
اپنے چہرے آئینوں میں، جب دیکھوگے، ڈر جاؤ گے

Ah The Hurdles in Research

2010-01-07T01:41:00.005-05:00

I have noted followings are harming my research work a lot..sharing with solutions as a note to myself..List is far from complete, but if I control these, may be it will make me little less of a lazy researcher...

Problem 1: Attraction of Technology

We get attracted to technology and run towards computers to provide for our social needs and more.

Solution: Select a time slot when your brain does your bidding (say 2am to 6am :) ). Promise not to use computers except only for research purposes during these hours. Promise.

Problem 2: Food

We suddenly start feeling that we are hungry, and call for pizza sounds most convincing.

Solution: Keep some portable food items (e.g. a pack of cookies) with you all the time. So you don't have to leave your work.

Problem 3: Got Stuck?

This perhaps the worst of the demons around, so many times you leave your work because you think you can't move any further at present.

Solution: Before you start working on a problem, instead make a list of problems you are going to work on. This way, when you get stuck on one, you start work on an other. Make sure problems are considerably different from each other. Make sure problems are interesting enough. It is important that you spend some time on making this list because these fifteen minute may save you a complete day, mind it!

Problem 4: Need for "Sleep" Underground

Sudden feeling that you have not had your quota of sleep today.

Solution: First of all, make schedule such that you could convince yourself that this is your "enemy" talking in your brain. Furthermore keep ready the coffee machine, and feel no shame in wielding this tool at times. Try Amphetamine too if situation worsens and it is legal in your country. After all Uncle Paul used it :)

Problem 5: Weather

Its bad weather, you can't get to your ideal place for work and your(/your roomies) car is broken.

Solution: Keep up with weather predictions. Furthermore keep all winter gear with you at all times. If you can party outdoors irrespective of it rains or shines, you surely can do work in your comfy office/study. Focus on your work, keep in mind that if you do it honestly you will feel elated even if it is thundering over your head.

And ...

What do you do when you are sad?

2010-01-06T22:42:00.003-05:00

Today while feeling very gloomy during a dinner with some friends(believe it!), I realized that I don't have any formal response to my feeling of sadness. I mean, for example, when I am angry then I know I can fight it by changing my posture (if I am standing, I should sit down and if I am sitting I would lie down) or I can drink some water to cool down; similarly if I am elated then I can use this energy to talk to new people, visit new places, learn new things etc. But I don't know, formally, what to do when my minds tries to close down because I am sad.

I threw the question around and was surprised to know that people actually have very competitive policies to handle this situation. I mention few of them here; I find the last one the least expected.

1. When people are sad, one response is to pass this time away in way that it hurts as little as possible. One of my friends, starts watching some movie. If the movie is good (not well defined, but lets just say if it has an intriguing story to tell) then mind catches it, and you have got one more thing to think about except for your gloominess. Which acts as a defensive shield and usually you are through.

2. Sadness is usually related to loneliness. An immediate response to which is to get connected. There are many ways to get connected, e.g. showing up at your friends doors, attending some social/religious meeting, Facebooking etc. But the one that was voted best is to call some old friend or distant family member you have not talked to since long and you remember enjoying their company.

3. The most unusual response that I learned today is to just feel sad! Argument is simple: sadness is a feeling like any other and is precious in its own, so why tarnish it with all this paraphernalia. Why not enjoying these few lonesome moments in their respect, as they are not going to last long anyway. How many people have time to feel sad today? So if you reject sadness, you are kind of training yourself to be less sensitive and in turn be less humane.

It reminds of something else. You know when it gets very cold, some people pick up a coffee cup and restrict themselves to their warm beds. Some others who have to stay out, put on all the winter gear in the world to fight back. A friend of mine, when it starts to snow, puts on shorts and an open-neck t, arm-bands her iPod and here she goes running on white roads, and after more than an hours show she texts me

"I guess I am somewhere at 95th, where is ColdStone?" :)

On a side note, What can be an appropriate response to feeling "blank"?

WITNESS: Failed state? Try Pakistan's M2 motorway

2009-12-16T20:14:00.000-05:00

http://www.reuters.com/article/idUSTRE5BF01220091216

WITNESS: Failed state? Try Pakistan's M2 motorway
Tue, Dec 15 2009
Alistair Scrutton first joined Reuters in 1998 as correspondent in Peru. Then he moved to Buenos Aires as senior correspondent for southern Latin America, covering coups in Bolivia, rebel violence in Peru and Argentina's 2001-2002 economic explosion which sparked the world's biggest sovereign debt default. Next, as Editor in Charge for Political And General News in Latin America he spearheaded coverage across the region. In 2007, he moved to India as chief correspondent, where he has focused on India's economic and political story as well as traveling to Afghanistan, Pakistan and Nepal. In the following story, Scrutton writes about his experiences driving down a Pakistani motorway, which is like a six-lane highway to paradise in a country that usually makes headlines for suicide bombers, army offensives and political mayhem.

By Alistair Scrutton

ISLAMABAD (Reuters) - If you want a slice of peace and stability in a country with a reputation for violence and chaos, try Pakistan's M2 motorway.

At times foreign reporters need to a give a nation a rest from their instinctive cynicism. I feel like that with Pakistan each time I whizz along the M2 between Islamabad and Lahore, the only motorway I know that inspires me to write.

Now, if the M2 conjures images of bland, spotless tarmac interspersed with gas stations and fast food outlets, you would be right. But this is South Asia, land of potholes, reckless driving and the occasional invasion of livestock.

And this is Pakistan, for many a "failed state." Here, blandness can inspire almost heady optimism.

Built in the 1990s at a cost of around $1 billion, the 228-mile (367-km) motorway -- which continues to Peshawar as the M1 -- is like a six-lane highway to paradise in a country that usually makes headlines for suicide bombers, army offensives and political mayhem.

Indeed, for sheer spotlessness, efficiency and emptiness there is nothing like the M2 in the rest of South Asia.

It puts paid to what's on offer in Pakistan's traditional foe and emerging economic giant India, where village culture stubbornly refuses to cede to even the most modern motorways, making them battlegrounds of rickshaws, lorries and cows.

There are many things in Pakistan that don't get into the news. Daily life, for one. Pakistani hospitality to strangers, foreigners like myself included, is another. The M2 is another sign that all is not what it appears in Pakistan, that much lies hidden behind the bad news.

On a recent M2 trip, my driver whizzed along but kept his speedometer firmly placed on the speed limit. Here in this South Asian Alice's Wonderland, the special highway police are considered incorruptible. The motorway is so empty one wonders if it really cuts through one of the region's most populated regions.

"130, OK, but 131 is a fine," said the driver, Noshad Khan. "The police have cameras," he added, almost proudly. His hand waved around in the car, clenched in the form of a gun.

On one of my first trips to Pakistan. I arrived at the border having just negotiated a one-lane country road in India with cows, rickshaws and donkey-driven carts.

I toted my luggage over to the Pakistan side, and within a short time my Pakistani taxi purred along the tarmac. The driver proudly showed off his English and played U.S. rock on FM radio. The announcer even had an American accent. Pakistan, for a moment, receded, and my M2 trip began.

Built in the 1990s by then prime minister Nawaz Sharif, it was part of his dream of a motorway that would unite Pakistan with Afghanistan and central Asia.

For supporters it shows the potential of Pakistan. Its detractors say it was a waste of money, a white elephant that was a grandiose plaything for Sharif.

But while his dreams for the motorway foundered along with many of Pakistan, somehow the Islamabad-Lahore stretch has survived assassinations, coups and bombs.

A relatively expensive toll means it is a motorway for the privileged. Poorer Pakistanis use the older trunk road nearby tracing an ancient route that once ran thousands of miles to eastern India. The road is shorter, busier and takes nearly an hour longer.

On my latest trip, I passed the lonely occasional worker in an orange suit sweeping the edge of the motorway in a seemingly Sisyphean task.

A fence keeps out the donkeys and horse-driven carts. Service centres are almost indistinguishable from any service station in the West, aside perhaps from the spotless mosques.

The real Pakistan can be seen from the car window, but in the distance. Colorful painted lorries still ply those roads. Dirt poor villagers toil in brick factories, farmers on donkey carts go about their business.

Of course, four hours of mundane travel is quite enough. Arriving in Lahore, the road suddenly turns into South Asia once again. Dust seeps through the open car window, endless honks sound, beggars knock on car windows. The driver begins again his daily, dangerous battle for road supremacy.

As Pakistan unveils itself in all its vibrancy, it is exciting to be back. But you can't help feel a tinge of regret at having experienced, briefly, a lost dream.

"Motorway good - but Pakistan," Noshad said at the last petrol station before we entered Lahore. "Terrorism, Rawalpindi," he added, referring to the latest militant attack on a mosque in the garrison town which killed dozens.

(Editing by Jerry Norton)

© Thomson Reuters 2009. All rights reserved. Users may download and print extracts of content from this website for their own personal and non-commercial use only. Republication or redistribution of Thomson Reuters content, including by framing or similar means, is expressly prohibited without the prior written consent of Thomson Reuters. Thomson Reuters and its logo are registered trademarks or trademarks of the Thomson Reuters group of companies around the world.

Thomson Reuters journalists are subject to an Editorial Handbook which requires fair presentation and disclosure of relevant interests.

مریم از یک نسبت عیسی عزیز

2009-12-10T05:39:00.003-05:00

در معنی اینکہ سیدة النساء فاطمة الزہراء
اسوہ کاملہ ایست برای نساء اسلام

مریم از یک نسبت عیسی عزیز
از سہ نسبت حضرت زہرا عزیز
نور چشم رحمة للعالمین
آن امام اولین و آخرین
آنکہ جان در پیکر گیتی دمید
روزگار تازہ آئین آفرید
بانوی آن تاجدار ’’ہل اتے‘‘
مرتضی مشکل گشا شیر خدا
پادشاہ و کلبہ ئی ایوان او
یک حسام و یک زرہ سامان او
مادر آن مرکز پرگار عشق
مادر آن کاروان سالار عشق
آن یکی شمع شبستان حرم
حافظ جمعیت خیرالامم
تا نشیند آتش پیکار و کین
پشت پا زد بر سر تاج و نگین
وان دگر مولای ابرار جہان
قوت بازوی احرار جہان
در نوای زندگی سوز از حسین
اہل حق حریت آموز از حسین
سیرت فرزند ہا از امہات
جوہر صدق و صفا از امہات
مزرع تسلیم را حاصل بتول
مادران را اسوۂ کامل بتول
بہر محتاجی دلش آنگونہ سوخت
با یہودی چادر خود را فروخت
نوری و ہم آتشی فرمانبرش
گم رضایش در رضای شوہرش
آن ادب پروردۂ صبر و رضا
آسیا گردان و لب قرآن سرا
گریہ ہای او ز بالین بی نیاز
گوہر افشاندی بدامان نماز
اشک او بر چید جبریل از زمین
ہمچو شبنم ریخت بر عرش برین
رشتۂ آئین حق زنجیر پاست
پاس فرمان جناب مصطفی است
ورنہ گرد تربتش گردیدمی
سجدہ ہا بر خاک او پاشیدمی
Iqbal-

The soil is in ferment, O friend

2009-12-10T00:15:00.002-05:00

The soil is in ferment, O friend

Behold the diversity.
The soil is the horse, so is the rider
The soil chases the soil, and we hear the clanging of soil
The soil kills the soil, with weapons of the soil.
That soil with more on it, is arrogance
The soil is the garden so is its beauty
The soil admires the soil in all its wondrous forms
After the circle of life is done it returns to the soil

...

by Bulleh Shah
(1680 - 1758)

English translation by
J. R. Puri and T. R. Shangari

Ah, Bagugosha is gone!

2009-12-01T17:56:00.003-05:00

Although I do not deny that it was with my consent, nevertheless it is with very heavy heart that I have to write that Bagugosha has been sacrificed on EID.
I have introduced him to you in an earlier post; he "is" my favorite billy, and perhaps the closest I have ever been to an animal.
My journey with Bagugosha started roughly the moment he came out his mothers tummy. I can still remember he surreal weightless tinny body pulsating on the ground. Within minutes, he mustered up courage to stand up by himself. It took him so much effort. He could not stretch his rear legs; clumsy as they looked, didn't seem to be able hold on to his weight. He tried, he fell down, again and again. It was sort of funny because he was not giving up at all. And after more an hour he was on his four. Walking took an hour or so.

He weaker and clumsier than his twin sis., which meant she would beat him in race for milk. We had to arrange an other goat to give him milk and that worked.
Once some metallic object hit him on leg and it looked pretty bad. He was crying because of pain, and he could not walk. I took him to the vet. Doc. who had clinic in an other town. It was farther-est he had been from home/mom, it was heart breaking carrying his tinder body in so much pain at so early an age: thanks God he survived the hurt.

I remember walking along with him in morning each day: in fact he was one who would wake up and sort of grab me towards door. Fellow didn't have any horns but he would fight every single male he would find on the way :)

He loved mangoes and would fight anyone for them. He would jump and skid, and hide and fight, and play. His presence always brought laughter and happiness to those close to him and his memories are so sweat and so saddening. I hope I will see him again: some other time, some other place!

That's all right. Anyway, my mum always said things we lose have a way of coming back to us in the end. --Luna Lovegood

DIMACS is 20!

2009-11-24T22:52:00.003-05:00

Last week we had DIMACS 20th birthday. Here are two writes on the event that I liked.

http://mysliceofpizza.blogspot.com/2009/11/dimacs-is-20.html

and

http://blog.computationalcomplexity.org/2009/11/dimacs-at-20.html

Happy 20 DIMACS!

-mudassir

SODA 2010 Accepted papers: abstracts

2009-09-06T00:57:00.003-04:00

source: http://soda10.cs.princeton.edu/

1. A PTAS for Minimum Clique Partition in Unit Disk Graphs
Authors: Imran Pirwani (Dept. of Computing Science, University of Alberta) Mohammad Salavatipour (Dept. of Computing Science, University of Alberta)
Topics: Algorithm Analysis, Approximation Algorithms, Geometry, Graph Algorithms

We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a polynomial time approximation scheme (PTAS) for this problem on UDG. In fact, we present a weakly-robust algorithm that given a graph G (not necessarily UDG) with edge-lengths, it either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within (1 + ε) ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG’s is NP-hard even if we are given edge lengths, our PTAS is a weakly-robust algorithm. Our main technical contribution involves showing the property of separability of an optimal clique partition: that there exists an optimal clique partition where the convex hulls of the cliques are pairwise non-overlapping. Our algorithm can be transformed into an O(log*n/ε^O(1)) time distributed polynomial-time approximation scheme (PTAS). Finally, we consider a weighted version of the clique partition problem on vertex weighted UDGs given given in the standard form (e.g. adjacency matrix); the weight of a clique is the weight of a heaviest vertex in it, and the weight of a clique partition is the sum of the weights of the cliques in it. This formulation generalizes the classical clique partition problem. We note some key distinctions between the weighted and the unweighted versions, where ideas developed for the unweighted case do not help. Yet, surprisingly, we show that the problem admits a (2 + ε)-approximation algorithm for the weighted version of the problem even when the graph is expressed in standard form. This improves on the best known algorithm which constructs an 8-approximation for the unweighted case for UDGs expressed in standard form.

2. An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling
Authors: Benjamin Moseley (University of Illinois Urbana-Champaign) Sungjin Im (University of Illinois Urbana-Champaign)
Topics: Algorithm Analysis, Approximation Algorithms, Online problems, Scheduling and Resource Allocation

In this paper the online pull-based broadcast model is considered. In this model, there are $n$ pages of data stored at a server and requests arrive for pages online. When the server broadcasts page $p$, all outstanding requests for the same page $p$ are simultaneously satisfied. We consider the problem of minimizing average (total) flow time online where all pages are unit-sized. For this problem, there has been a decade-long search for an online algorithm which is scalable, i.e. $(1+\eps)$-speed $O(1)$-competitive for any fixed $\eps >0$. Before this work, no known online algorithm was a candidate to be scalable. In this paper, we develop a new algorithm for this problem and give the first analysis of an online scalable algorithm.

3. Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications
Authors: Anthony Man-Cho So (The Chinese University of Hong Kong)
Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization

We consider the problem of detecting a vector of symbols that is being transmitted over a fading multiple-input multiple-output (MIMO) channel, where each symbol is an $M$-th root of unity for some fixed $M \ge 2$. Although the symbol vector that minimizes the error probability can be found by the so-called maximum-likelihood (ML) detector, its computation is intractable in general. In this paper we analyze a popular polynomial-time heuristic, called the semidefinite relaxation (SDR) detector, for the problem and establish its first non-asymptotic performance guarantee. Specifically, in the low signal-to-noise ratio (SNR) region, we show that for any $M \ge 2$, the SDR detector will yield a constant factor approximation to the optimal log-likelihood value with a probability that increases exponentially fast to $1$ as the channel size increases. In the high SNR region, it is known that for $M=2$, the SDR detector will yield an exact solution to the ML detection problem with a probability that converges to $1$. We refine this result by establishing the rate of convergence. Our work can be viewed as an average-case analysis of a certain SDP relaxation, and the input distribution we use is motivated by physical considerations. Our results also refine and extend those in previous work, which are all asymptotic in nature and apply only to the problem of detecting binary (i.e. when $M=2$) vectors. In particular, our results can give better insight into the performance of the SDR detector in practical settings.

An Improved Construction of Progression-Free Sets
Authors: Michael Elkin (Ben-Gurion University of the Negev)
Topics: Combinatorics, Geometry, Number Theory

The problem of constructing dense subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = Omega(n^{\log_3 2}) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} \cdot \log^{1/4} n}}). Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend was reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(sqrt{log n}), and shows that |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} }} \cdot \log^{1/4} n \right). In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained. Also, the construction can be implemented by an efficient algorithm. Behrend's construction has numerous applications in Theoretical Computer Science. In particular, it is used for fast matrix multiplication, for property testing, and in the area of communication complexity. Plugging in our construction instead of Behrend construction in the matrix multiplication algorithm of Coppersmith and Winograd improves the state-of-the-art upper bound on the complexity of the matrix multiplication by a factor of log^\nu n, for some fixed constant \nu > 0. We also present an application of our technique in Computational Geometry.

Solving the Replacement Paths Problem for Planar Directed Graphs in O(n*log n) Time
Authors: Christian Wulff-Nilsen (Department of Computer Science, University of Copenhagen)
Topics: Algorithm Analysis, Graph Algorithms, Graph Theory, Internet and Network Algorithms, Optimization

In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(n*log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n*(log n)^2).

Correlation Clustering with Noisy Input
Authors: Claire Mathieu (Brown University) Warren Schudy (Brown University)
Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming, Optimization, Probability, Random Graphs

Correlation clustering is a type of clustering that uses a basic form of input data: For every pair of data items, the input specifies whether they are similar (belonging to the same cluster) or dissimilar (belonging to different clusters). This information may be inconsistent, and the goal is to find a clustering (partition of the vertices) that disagrees with as few pieces of information as possible. Correlation clustering is APX-hard for worst-case inputs. We study the following semi-random noisy model to generate the input: start from an arbitrary partition of the vertices into clusters. Then, for each pair of vertices, the similarity information is corrupted (noisy) independently with probability $p$. Finally, an adversary generates the input by choosing similarity/dissimilarity information arbitrarily for each corrupted pair of vertices. In this model, our algorithm produces a clustering with cost at most $1 + O(n^{-1/6})$ times the cost of the optimal clustering, as long as $ p <= 1/2 - n^{-1/3}$. Moreover, if the noise $p$ is small, that is, $p=O(n^{-\epsilon})$, then we can exactly reconstruct all clusters of the planted clustering that have size $\Omega(1/\epsilon)$, and provide a certificate (witness) proving that those clusters are in any optimal clustering. Among other techniques, we use the natural semi-definite programming relaxation followed by an interesting rounding phase. The analysis uses semi-definite programming duality and spectral properties of random matrices.

A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs Authors: Aaron Bernstein (MIT)
Topics: Approximation Algorithms, Graph Algorithms

Let $G = (V,E)$ be a directed graph with non-negative edge weights, let $s,t$ be two specified vertices in this graph, and let $\pi(s,t)$ be the shortest path between them. In the \emph{replacement paths} problem we want to compute, for every edge $e$ on $\pi(s,t)$, the shortest path from $s$ to $t$ that avoids $e$. The naive solution to this problem would be to remove each edge $e$, one at a time, and compute the shortest $s-t$ path each time; this yields a running time of $O(mn + n^2\log n)$. Gotthilf and Lewenstein \cite{GL09} recently improved this to $O(mn + n^2\log\log n)$, but no $o(mn)$ algorithms are known. \\ \\ We present the first \emph{approximation} algorithm for replacement paths in weighted, directed graphs. Given any $\eps \in [0, 1)$, our algorithm returns $\oeps$-approximate replacement paths in $O(\eps^{-1}\log^2 n \log(nC/c)(m + n\log n)) = \widetilde{O}(m\log(nC/c)/\eps)$ time, where $C$ is the largest edge weight in the graph and $c$ is the smallest positive weight. \\ \\ We also present an even faster $\oeps$ approximate algorithm for the simpler problem of approximating the $k$ shortest simple $s-t$ paths in a graph. That is, our algorithm outputs $k$ different simple $s-t$ paths, where the kth path we output is a $\oeps$ approximation to the actual kth shortest simple $s-t$ path. The running time of our algorithm is $O(k \eps^{-1} \log^2 n (m + n\log n)) = \wo(km/\eps)$. The fastest \emph{exact} algorithm for this problem has a running time of $O(k(mn + n^2\log\log n)) = \wo(kmn)$ \cite{GL09}. The previous best approximation algorithm was developed by Roditty \cite{R07}; it has a stretch of $3/2$ and a running time of $\wo(km\sqrt{n})$ (it does not work for replacement paths). \\ \\ Note that all of our running times are nearly optimal except for the $O(\log(nC/c))$ factor in the replacement paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges.

A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics
Authors: T-H. Hubert Chan (Max-Planck-Institut fuer Informatik) Khaled Elbassioni (Max-Planck-Institut fuer Informatik)
Topics: Algorithm Analysis, Approximation Algorithms, Optimization

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of $n$ subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call $\alpha$-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell~\cite{M07} and the QPTAS for TSP on doubling metrics by Talwar~\cite{Tal04}. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing.
Authors: Aparna Das (Brown University) Claire Mathieu (Brown University)
Topics: Approximation Algorithms, Graph Algorithms

In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.

Fully-Functional Succinct Trees
Authors: Kunihiko Sadakane (National Institute of Informatics) Gonzalo Navarro (University of Chile)
Topics: Compression, Data Structures

We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + o(n)$ bits and various operations on the tree can be supported in constant time under the word-RAM model. However existing data structures are not satisfactory in both theory and practice because (1) the lower-order term is $\Omega(n \log\log n/\log n)$ and cannot be neglected, (2) the hidden constant is also large, and (3) the data structures are complicated and difficult to be implemented. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature, to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving $2n + O(n /\polylog(n))$ bits of space. The redundancy is significantly lower than any previous proposal, and the data structure is easily implemented.

Online Learning with Queries
Authors: Chao-Kai Chiang (Academia Sinica) Chi-Jen Lu (Academia Sinica)
Topics: Learning, Online problems, Probability

In the standard online learning problem, a player has to iteratively choose an action before knowing anything about the corresponding loss. However, there are situations in which it seems possible for the player to spend some effort or resources to collect some prior information before her action. This motivates us to study a variant of the online learning problem, in which the player is allowed to query $B$ bits from the loss vector in each iteration before choosing her action. We provide an algorithm for this problem. Suppose each loss value is represented by $K$ bits and distinct loss values differ by at least $\delta$, and suppose there are $N$ actions to choose and $T$ rounds to play. Then our algorithm achieves a regret of the following form. Before $B$ approaching $B_1 = NK/2$, the regret stays at $O(\sqrt{T \ln N})$, and after $B$ exceeding $B_1$ but before approaching $B_2 = NK/2 + 3K - 1$, the regret drops slightly to $O(\sqrt{(T\ln N)/N})$, while after $B$ exceeding $B_2$, the regret takes a dramatic drop to $(N\ln N)/\delta$. Our algorithm is in fact close to optimal as we also provide a regret lower bound which almost matches the regret upper bound achieved by the algorithm.

On the Exact Space Complexity of Sketching and Streaming Small Norms
Authors: Daniel M. Kane (Harvard University) Jelani Nelson (MIT) David P. Woodruff (IBM Almaden)
Topics: Streaming Algorithms

We settle the 1-pass space complexity of (1+eps)-approximating the Lp norm, for real p with 1 <= p <= 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [-M, M]. In particular, we show the space required is Theta(eps^{-2}*log(mM) + loglog(n)) bits. Our result also holds for 0 < g="(V,E)" x="R" q =" \left\{">0. We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), matching the best known ones, but whose analysis also bounds the integrality gap of the LP relaxation of ATSPP by the same factor. This solves an open problem posed by Chekuri and Pal (2007). We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)-approximation to the directed latency problem. This also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce. We note that this is essentially the best possible ratio unless an asymptotically better approximation exists for the well-studied asymmetric traveling salesman tour problem.

Data Structures for Range Minimum Queries in Multidimensional Arrays
Authors: Hao Yuan (Purdue University) Mikhail J. Atallah (Purdue University)
Topics: Algorithm Analysis, Data Structures, Geometry, Pattern Matching

Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-time query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time. This improves the preprocessing time over all previous work under the same model, i.e., RAM with logarithmic word size.

Incentive Compatible Budget Elicitation in Multi-unit Auctions
Authors: Sayan Bhattacharya (Duke University) Vincent Conitzer (Duke University) Kamesh Munagala (Duke University) Lirong Xia (Duke University)
Topics: Economics, Mechanism Design

In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski et al show that the adaptive clinching auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show that this auction is not truthful with private budgets, so that there is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that the adaptive clinching auction is incentive compatible when over-reporting the budget is not possible (for instance, when funds must be shown upfront). We can also make reporting larger budgets suboptimal with a small randomized modification to the auction. In either case, this makes the modified auction Pareto-optimal with private budgets. We also show that the Budget Monotonicity property does not hold for auctioning indivisible units of the good, showing a sharp contrast between the divisible and indivisible cases. The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction. Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization. We show the approximation result via designing a rounding scheme for an LP relaxation of the problem, which may be of independent interest.

Sharp kernel clustering algorithms and their associated Grothendieck inequalities
Authors: Subhash Khot (Courant Institute) Assaf Naor (Courant Institute)
Topics: Algorithm Analysis, Approximation Algorithms, Complexity, Geometry, Learning, Optimization

In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric positive semidefinite matrix $B=(b_{ij})$. The goal is to find a partition $\{S_1,\ldots,S_k\}$ of $\{1,\ldots n\}$ which maximizes $ \sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}$. We design a polynomial time approximation algorithm that achieves an approximation ratio of $\frac{R(B)^2}{C(B)}$, where $R(B)$ and $C(B)$ are geometric parameters that depend only on the matrix $B$, defined as follows: if $b_{ij} = \langle v_i, v_j \rangle$ is the Gram matrix representation of $B$ for some $v_1,\ldots,v_k\in \R^k$ then $R(B)$ is the minimum radius of a Euclidean ball containing the points $\{v_1, \ldots, v_k\}$. The parameter $C(B)$ is defined as the maximum over all measurable partitions $\{A_1,\ldots,A_k\}$ of $\R^{k-1}$ of the quantity $\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle$, where for $i\in \{1,\ldots,k\}$ the vector $z_i\in \R^{k-1}$ is the Gaussian moment of $A_i$, i.e., $z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx$. We also show that for every $\eps > 0$, achieving an approximation guarantee of $(1-\e)\frac{R(B)^2}{C(B)}$ is Unique Games hard.

On the Optimality of Spiral Search
Authors: Elmar Langetepe (University of Bonn, Institute of Computer Science I)
Topics: Algorithm Analysis, Combinatorics, Complexity, Geometry, Online problems

Searching for a point in the plane is a well-known search game problem introduced in the early eigthies. The best known search strategy is given by a spiral and achieves a \emph{competitive ratio} of $17.289\ldots$ It was shown by Gal \cite{g-sg-80} that this strategy is the best strategy among all \emph{monotone} and \emph{periodic} strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continous version of the well-known $m$-ray search problem and also appears in several non-geometric applications and modifications. Therefore the optimality of spiral search is an important questions considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical $m$-ray search.

Cell-probe lower bounds for prefix sums and matching brackets
Authors: Emanuele Viola (Northeastern University)
Topics: Combinatorics, Complexity, Data Structures, Databases and Information Retrieval

We prove that to store n bits x0... x1 so that each prefix sum (a.k.a. rank) query Sum(i) := {k <> 0, problem p-FOA is strongly NP-hard. *) Even the special case with equi-distant cameras is strongly NP-hard. This settles a question left open in Isler et al. (2005). As our main contribution, we fully resolve the approximability status of p-FOA: *) For every real p, problem p-FOA possesses a PTAS. Our PTAS extends the results and ideas of Isler et al. (2005) for the equi-distant special case. The design of our PTAS is quite intricate, and introduces a number of new ideas to the area. Reference: V. Isler, S. Khanna, J.R. Spletzer, C.J. Taylor (2005). Target tracking with distributed sensors: The focus of attention problem. Computer Vision and Image Understanding 100, 225--247.

A locality-sensitive hash for real vectors
Authors: Tyler Neylon (Bynomial, Inc.)
Topics: Approximation Algorithms, Databases and Information Retrieval, Geometry, Optimization

We present a simple and practical algorithm for the $c-$approximate near neighbor problem ($c-$NN): given $n$ points $P\subset\R^d$ and radius $R$, build a data structure which, given $q\in\R^d$, can with probability $1-\delta$ return a point $p\in P$ with $\mathsf{dist}(p,q)\le cR$ if there is any $p^*\in P$ with $\mathsf{dist}(p^*,q)\le R$. For $c=d+1$, our algorithm deterministically ($\delta=0$) preprocesses in time $O(nd\log d)$, space $O(dn)$, and answers queries in expected time $O(d^2)$; this is the first known algorithm to deterministically guarantee an $O(d)-$NN solution in constant time with respect to $n$ for all $\ell_p$ metrics. A probabilistic version empirically achieves useful $c$ values ($c < t="O(d^2\log{n})$)" t="O(d^2\log{n})$" d="O(\log{n}/\log\log{n})$." k="b(1+o_b(1))/\ln{b}." k="Cb/\ln{b}" c="1" s =" n," i="1,2,\dots,k$." k="O((\log"> 0$. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymour's. In addition, if an input graph $G$ is either $4$-edge-connected planar or Eulerian planar, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k = O((\log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. Moreover, if an input graph is either $4$-edge-connected $H$-minor-free or Eulerian $H$-minor-free, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k=O((\log \log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. (3) We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is $O(n^2)$, which is faster than Robertson and Seymour's.

Coresets and Sketches for High Dimensional Subspace Approximation Problems
Authors: Dan Feldman (School of Computer Science; Tel Aviv University; Tel Aviv 69978, Israel) Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) Christian Sohler (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA)
Topics: Approximation Algorithms, Geometry, Learning, Streaming Algorithms, Sublinear Algorithms

Given a point set $P$ in $\REAL^d$, an $F_q(\ell_p)$-subspace approximation problem asks for a subspace that minimizes the sum of $q$-th powers of $\ell_p$-distances to this subspace. In this paper we develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set $P$ with respect to a subspace approximation problem. Our results are: \begin{itemize} \item A dimensionality reduction method that can be applied to $F_q(\ell_p)$-clustering and shape fitting problems \cite{DDHKM09, Har06c}. \item The first strong coreset for $F_1(\ell_2)$-subspace approximation in high dimensional spaces, i.e. of size polynomial in the dimension of the space. \item A $(1+\epsilon)$-approximation algorithm for the $j$-dimensional $F_1(\ell_2)$-subspace approximation problem with running time $O(nd (j/\eps)^{O(1)} + (n+d) 2^{O(j/\epsilon)^{O(1)}})$. \item A streaming algorithm that maintains a coreset for the $F_1(\ell_2)$-subspace approximation problem and uses $\tilde{O}(d(\frac{j2^{ O(\sqrt{\log n})}}{\epsilon^2})^{\poly(j)})$ space, where the space gives the number of memory cells used. \item Several streaming algorithm with bounded precision in the turnstile model. We significantly extend the results of \cite{CW09} for approximate linear regression, distance to subspace approximation, and best rank-$j$ approximation, to error measures other than the Frobenius norm, obtaining $1$-pass sublinear, near-optimal space complexity for these problems. Our time is always polynomial for constant $j/\eps$, even for the time to extract a $(1+\eps)$-approximation to the best rank-$j$ subspace from the sketch. \end{itemize} =========================================================================== 1-pass Relative-Error L_p-Sampling with Applications --------------------------------------------------------------------------- Authors: Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA) Topics: Streaming Algorithms --------------------------------------------------------------------------- For any p in [1,2], we give a 1-pass poly((log n)/epsilon)-space algorithm which, given a data stream of length m with insertions and deletions of an n-dimensional vector a with updates in the range {-M, -M+1, ..., M-1, M} outputs a sample of {1, 2, ..., m} for which for all i the probability that i is returned is (1 +- epsilon)|a_i|^p/F_p(a) + n^{-C}, where a_i denotes the (possibly negative) value of coordinate i, F_p(a) = sum_{i=1}^m |a_i|^p = ||a||_p^p denotes the p-th frequency moment (i.e., the p-th power of the L_p norm), and C > 0 is an arbitrarily large constant. Here we assume that n,m, and M are polynomially related. Our generic sampling framework improves and unifies algorithms for several communication and streaming problems, including cascaded norms, heavy hitters, and moment estimation. It also gives the first relative-error forward sampling algorithm in a data stream with deletions, answering an open question of Cormode et al. =========================================================================== One-Counter Markov Decision Processes --------------------------------------------------------------------------- Authors: Tomas Brazdil (Faculty of Informatics, Masaryk University) Vaclav Brozek (Faculty of Informatics, Masaryk University) Kousha Etessami (School of Informatics, University of Edinburgh) Antonin Kucera (Faculty of Informatics, Masaryk University) Dominik Wojtczak (CWI, Amsterdam) Topics: Complexity, Game Theory, Markov Chains, Optimization, Probability --------------------------------------------------------------------------- We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs extend finite-state MDPs with an unbounded counter. The counter can be incremented, decremented, or not changed during each state transition, and transitions may be enabled or not depending on both the current state and on whether the counter value is 0 or not. Some states are ``random'', from where the next transition is chosen according to a given probability distribution, while other states are ``controlled'', from where the next transition is chosen by the controller. Different objectives for the controller give rise to different computational problems, aimed at computing optimal achievable objective values and optimal strategies. OC-MDPs are in fact equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a purely stochastic model heavily studied in queueing theory and applied probability. They can thus be viewed as a natural ``adversarial'' extension of a classic stochastic model. They can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. OC-MDPs also subsume (as a very restricted special case) a recently studied MDP model called ``solvency games'' that model a risk-averse gambling scenario. Basic computational questions for OC-MDPs include ``termination'' questions and ``limit'' questions, such as the following: does the controller have a strategy to ensure that the counter (which may, for example, count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (a.s.)? Or that the counter will have lim sup value infinity, a.s.? Or, that it will hit value 0 in a selected terminal state, a.s.? Or, in case such properties are not satisfied almost surely, compute their optimal probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. Specifically, we show that several quantitative and almost-sure limit problems can be answered in polynomial time, and that almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is PSPACE-hard and we provide an exponential time algorithm for this problem. We also characterize classes of strategies that suffice for optimality in several of these settings. Our upper bounds combine a number of techniques from the theory of MDP reward models, the theory of random walks, and a variety of automata-theoretic methods. =========================================================================== How far can you reach? --------------------------------------------------------------------------- Authors: Ciprian Borcea (Dept. of Mathematics, Rider University) Ileana Streinu (Computer Science Department, Smith College) Topics: Geometry, Metric Embeddings, Robotics --------------------------------------------------------------------------- Robot Arm Reachability, the problem of computing the extremal configurations of a 3D revolute-jointed manipulator, is a long standing open problem in Robotics. In this paper we completely solve it for orthogonal polygonal chains, which appear as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available. These were not even guaranteed to produce the optimum; in fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. We present surprisingly elementary and efficient (mostly linear time) algorithms for four fundamental problems: (1) finding the minimum and the maximum reach value, (2) finding an extremal configuration (or enumerating all of them), (3) folding a given chain to a given extremal position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. Our theoretical results reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar Carpenter's Rule Problem. =========================================================================== Region growing for multi-route cuts --------------------------------------------------------------------------- Authors: Shuchi Chawla (University of Wisconsin - Madison) Siddharth Barman (University of Wisconsin - Madison) Topics: Approximation Algorithms, Graph Algorithms, Optimization --------------------------------------------------------------------------- We study a number of \emph{multi-route cut} problems: given a graph $G=(V,E)$ and connectivity thresholds $k_{(u,v)}$ on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair $(u,v)$ to strictly below its given threshold. These problems arise in the context of reliability in communication networks; They are natural generalizations of traditional minimum cut problems where the thresholds are either $1$ (we want to completely separate the pair) or $\infty$ (we don't care about the connectivity for the pair). We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either $2$ or $\infty$ (the ``$2$-route cut'' case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithms achieving different cost-connectivity tradeoffs. =========================================================================== Faster exponential time algorithms for the shortest vector problem --------------------------------------------------------------------------- Authors: Daniele Micciancio (University of California, San Diego) Panagiotis Voulgaris (University of California, San Diego) Topics: Algorithm Analysis, Cryptography, Experimental Algorithmics --------------------------------------------------------------------------- We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar and Sivakumar [Proceedings of STOC 2001] which was shown by Nguyen and Vidick [J. Math. Crypto. 2(2):181--207] to run in time $2^{5.9n}$ and space $2^{2.95n}$. We also present a practical variant of our algorithm which provably uses an amount of space proportional to $\tau_n$, the ``kissing'' constant in dimension $n$. Based on the best currently known upper and lower bounds on the kissing constant, the space complexity of our second algorithm is provably bounded by $2^{0.41n}$, and it is likely to be at most $2^{0.21n}$ in practice. No upper bound on the running time of our second algorithm is currently known, but experimentally the algorithm seems to perform fairly well in practice, with running time $2^{0.48n}$, and space complexity $2^{0.18n}$. =========================================================================== Finding the Jaccard Median --------------------------------------------------------------------------- Authors: Flavio Chierichetti (Sapienza University of Rome) Ravi Kumar (Yahoo! Research Santa Clara) Sandeep Pandey (Yahoo! Research Santa Clara) Sergei Vassilvitskii (Yahoo! Research New York) Topics: Approximation Algorithms, Optimization --------------------------------------------------------------------------- The median problem in the weighted Jaccard metric was analyzed for the first time by Sp\"ath in 1981. Up until now, only an exponential-time exact algorithm was known. We (a) show that the problem does not admit a FPTAS (assuming P $\ne$ NP), even when restricted to binary vectors and (b) give a PTAS for the general weighted Jaccard metric. The PTAS leverages of a number of different algorithmic ideas and our hardness result makes use of a gadget which appears to be ``unique'' in interesting ways. =========================================================================== The scaling window for a random graph with a given degree sequence --------------------------------------------------------------------------- Authors: Hamed Hatami (University of Toronto) Michael Molloy (University of Toronto) Topics: Graph Theory, Random Graphs --------------------------------------------------------------------------- We consider a random graph on a given degree sequence $D$, satisfying certain conditions. We focus on two parameters $Q=Q(D), R=R(D)$. Molloy and Reed proved that $Q=0$ is the threshold for the random graph to have a giant component. We prove that if $|Q|=O(n^{-1/3} R^{2/3})$ then, with high probability, the size of the largest component of the random graph will be of order $\Theta(n^{2/3}R^{-1/3})$. If $Q$ is asymptotically larger/smaller that $n^{-1/3}R^{2/3}$ then the size of the largest component is asymptotically larger/smaller than $n^{2/3}R^{-1/3}$. In other words, we establish the scaling window. =========================================================================== Energy Efficient Scheduling for Data Centers via Partial Shutdown --------------------------------------------------------------------------- Authors: Samir Khuller (University of Maryland) Jian Li (University of Maryland) Barna Saha (University of Maryland) Topics: Approximation Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- Motivated by issues of saving energy in data centers we define a collection of new problems referred to as ``machine activation'' problems. The central framework we introduce considers a collection of $m$ machines (unrelated or related) with each machine $i$ having an {\em activation cost} of $a_i$. There is also a collection of $n$ jobs that need to be performed and $p_{ij}$ is the processing time of job $j$ on machine $i$. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of $A$ -- we would like to {\em select} a subset $S$ of the machines to activate with total cost $a(S) \le A$ and {\em find} a schedule for the $n$ jobs on the machines in $S$ minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine $i$ has cost $a_i$ and speed $s_i$, and the processing time of job $j$ on machine $i$ is $p_{ij} = \frac{p_j}{s_i}$, where $p_j$ is the processing requirement of job $j$. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan $T(A)$ and activation cost $A$ then we can obtain a schedule with makespan $\makespanconstant T(A)$ and activation cost $\costconstant A$, for any $\epsilon >0$. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. For the uniformly related parallel machine scheduling problem, we develop a polynomial time scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most $A$ and the makespan is at most $(1+\epsilon) T(A)$ for any $\epsilon >0$. For the special case of $m$ identical speed machines, the machine activation problem is trivial, since the cheapest subset of $k$ machines is always the best choice if the optimal solution activates $k$ machines. In addition, we consider the case when some jobs can be dropped (and are treated as outliers). =========================================================================== Sharp Dichotomies for Regret Minimization in Metric Spaces --------------------------------------------------------------------------- Authors: Robert Kleinberg (Cornell University) Aleksandrs Slivkins (Microsoft Research (SVC)) Topics: Algorithm Analysis, Learning, Online problems, Optimization --------------------------------------------------------------------------- The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on the difference in expected payoff between certain pairs of strategies. Classical results of Lai and Robbins and Auer et al imply a logarithmic regret bound for the Lipschitz MAB problem on finite metric spaces. Recent results on continuum-armed bandit problems and their generalizations imply lower bounds of $\sqrt{t}$, or stronger, for many infinite metric spaces such as the unit interval. Is this dichotomy universal? We prove that the answer is yes: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in \omega(\log t)$, or bounded below by any $g\in o(\sqrt{t})$. Perhaps surprisingly, this dichotomy does not coincide with the distinction between finite and infinite metric spaces; instead it depends on whether the completion of the metric space is compact and countable. Our proof connects upper and lower bound techniques in online learning with classical topological notions such as perfect sets and the Cantor-Bendixson theorem. We also consider the "full-feedback" (a.k.a., "best-expert") version of Lipschitz MAB problem, termed the "Lipschitz experts problem", and show that this problem exhibits a similar dichotomy. We proceed to give nearly matching upper and lower bounds on regret in the Lipschitz experts problem on uncountable metric spaces. These bounds are of the form $\tilde{\Theta}(t^\gamma)$, where the exponent $\gamma\in [\tfrac12, 1]$ depends on the metric space. To characterize this dependence, we introduce a novel dimensionality notion tailored to the experts problem. Finally, we show that both Lipschitz bandits and Lipschitz experts problems become completely intractable (in the sense that no algorithm has regret $o(t)$) if and only if the completion of the metric space is non-compact. =========================================================================== Lower Bounds for Sparse Recovery --------------------------------------------------------------------------- Authors: khanh do ba (MIT CSAIL) piotr indyk (MIT CSAIL) eric price (MIT CSAIL) Topics: Approximation Algorithms, Coding Theory, Compression, Geometry, Information Theory, Streaming Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For an n-dimensional vector x, its *sketch* is equal to Ax, where A is an m x n matrix, possibly chosen at random. Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains plenty of information about x. A particularly useful and well-studied problem is that of sparse recovery: given Ax, recover a k-sparse vector x* (with at most k non-zeros) such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some norm parameters p and q and an approximation factor C=C(k). Sparse recovery has numerous applications to areas such as data stream computing and compressed sensing. It is known that there exist matrices A that achieve the above guarantee with p=q=1 and constant C (in fact, even somewhat stronger bounds), with sketch length m=O(k log (n/k)). However, perhaps surprisingly, it is not known if this bound can be improved any further, even though matching lower bounds are known for specific *algorithms*, specific *matrix types*, or other recovery scenarios (e.g., involving measurement noise). The lack of tight lower bounds represents a major gap in our understanding of the problem. In this paper we make significant progress on this issue. In particular we show that: - in the deterministic case, where we require one matrix A to work for all signals x, we show a tight lower bound of Omega(k log (n/k)), thus resolving the issue completely - in the randomized case, where we require that a matrix A chosen at random from some distribution should work for a *fixed* vector x with probability at least 1-1/n, we show a lower bound of Omega(log n / log log n) =========================================================================== The Complexity of Guarding Terrains --------------------------------------------------------------------------- Authors: James King (McGill University) Erik Krohn (University of Iowa) Topics: Complexity, Geometry --------------------------------------------------------------------------- A set G of points on a 1.5-dimensional terrain, also known as an x-monotone polygonal chain, is said to guard the terrain if any point on the terrain is ‘seen’ by a point in G. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. Our proof uses a reduction from PLANAR 3-SAT. We build gadgets capable of ‘mirroring’ a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5-dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3-SAT to find very specific operations involving only ‘adjacent’ variables. For these restricted operations we can construct gadgets that allow a full reduction to work. =========================================================================== An (almost) Linear Time Algorithm For Odd Cycles Transversal --------------------------------------------------------------------------- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics) Bruce Reed (McGill University) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- We consider the following problem, which is called the odd cycles transversal problem. Input: A graph G and an integer k. Output : A vertex set X \in V(G) with at most k vertices such that G-X is bipartite. We present an O(m \alpha(m,n)) time algorithm for this problem for any fixed k, where n,m are the number of vertices and the number of edges, respectively, and the function \alpha(m,n) is the inverse of the Ackermann function. This improves the time complexity of the algorithms by Reed, and by Reed, Smith and Vetta who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X' \in E(G) such that G-X' is bipartite. Using this algorithm and our recent result(SODA'09), we give an O(m \alpha(m,n) + n \log n) algorithm for the following problem for any fixed k: Input: A graph G and an integer k. Output : Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C_1,\dots,C_k in G such that each vertex is on at most two of these odd cycles. We also give a simpler proof for the following result by Reed. The Erd\H{o}s-P\'osa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G-X is bipartite for some function f of k. Note that the Erd\H{o}s-P\'osa property does not hold for odd cycles in general. =========================================================================== Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Georgia Institute of Technology) Daniel Dadush (Georgia Institute of Technology) Santosh Vempala (Georgia Institute of Technology) Topics: Geometry, Markov Chains, Probability --------------------------------------------------------------------------- Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an ecient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard. =========================================================================== Resource Minimization for Fire Containment --------------------------------------------------------------------------- Authors: Parinya Chalermsook (University of Chicago) Julia Chuzhoy (TTI-C) Topics: Approximation Algorithms, Graph Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- We consider the following model for fire containment. We are given an undirected graph G=(V,E) with a source vertex s where the fire starts. At each time step, firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease, and its containment via vaccination. In this paper we focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to any vertex of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an $O(\log^*n)$-approximation algorithm for RMFC on trees, by rounding a natural linear programming relaxation of the problem. We also show that an even stronger LP relaxation has an integrality gap of $\Omega(\log^*n)$ on trees. Finally, we consider RMFC on directed layered graphs, and show an O(\log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation. =========================================================================== Price of Anarchy for Greedy Auctions --------------------------------------------------------------------------- Authors: Brendan Lucier (University of Toronto) Allan Borodin (University of Toronto) Topics: Approximation Algorithms, Game Theory, Mechanism Design --------------------------------------------------------------------------- We consider mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, profit-maximizing scheduling, and others. We study the price of anarchy for such mechanisms, which is a bound on the approximation ratio obtained at any mixed Nash equilibrium. We demonstrate that a broad class of greedy approximation algorithms can be implemented as mechanisms for which the price of anarchy nearly matches the performance of the original algorithm. This is true even in Bayesian settings, where the agents' valuations are drawn from publicly known distributions. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for these mechanisms. For many problems, the approximation factors obtained at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for the general combinatorial auction with $O(\sqrt{m})$ price of anarchy. =========================================================================== Inapproximability for planar embedding problems --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Anastasios Sidiropoulos (University of Toronto) Anastasios Zouzias (University of Toronto) Topics: Approximation Algorithms, Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We consider the problem of computing a minimum-distortion bijection between two point-sets in R^2. We prove the first non-trivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 < k="2$"> Topics: Combinatorics, Learning --------------------------------------------------------------------------- In this paper, we consider the problem of reconstructing a hidden graph with $m$ edges using additive queries. Given a graph $G=(V,E)$ and a set of vertices $S\subseteq V$, an additive query, $Q(S)$, asks for the number of edges in the subgraph induced by $S$. The information theoretic lower bound for the query complexity of reconstructing a graph with $n$ vertices and $m$ edges is $$ O\left(\frac{m\log \frac{n^2}{m}}{\log m}\right).$$ In this paper we give the first polynomial time algorithm with query complexity that matches this lower bound\footnote{In this paper, by optimal we mean asymptotically. That is, up to a constant factor.}. This solves the open problem by [S. Choi and J. Han Kim. Optimal Query Complexity Bounds for Finding Graphs. \emph{STOC} ,749--758 ,2008]. In the paper, we actually show an algorithm for the generalized problem of reconstructing weighted graphs. In the weighted case, an additive query, $Q(S)$, asks for the sum of weights of edges in the subgraph induces by $S$. The complexity of the algorithm also matches the information theoretic lower bound. =========================================================================== EDF-schedulability of synchronous periodic task systems is coNP-hard --------------------------------------------------------------------------- Authors: Friedrich Eisenbrand (Institute of Mathematics, EPFL, Lausanne, Switzerland) Thomas Rothvoß (Institute of Mathematics, EPFL, Lausanne, Switzerland) Topics: Complexity, Number Theory, Scheduling and Resource Allocation --------------------------------------------------------------------------- In the synchronous periodic task model, a set T_1,...,T_n of tasks is given, each releasing jobs of running time c_i and relative deadline d_i at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i <= p_i, the EDF-schedule is feasible if and only if \[ \forall Q >= 0: \sum_{i=1}^n (\floor{(Q-d_i)/p_i} + 1) * c_i <= Q. \] Despite of an enormous amount of literature dealing with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation. =========================================================================== Algorithmic Lower Bounds for Problems Parameterized by Clique-width --------------------------------------------------------------------------- Authors: Fedor V. Fomin (University of Bergen) Petr A. Golovach (University of Bergen) Daniel Lokshtanov (University of Bergen) Saket Saurabh (University of Bergen) Topics: Algorithm Analysis, Complexity, Graph Algorithms --------------------------------------------------------------------------- Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most $t$, then there are many natural problems for which the running time of the best known algorithms is of the form $n^{f(t)}$, where $n$ is the input length and $f$ is some function. It was an open question whether natural problems like Graph Coloring, Max-Cut, Edge Dominating Set, and Hamiltonian Path are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [SODA 2009], we showed that unless $FPT\neqW[1]$, there is no algorithm with run time $O(g(t)\cdot n^c)$, for some function $g$ and a constant $c$ not depending on $t$, for Graph Coloring, Edge Dominating Set and Hamiltonian Path. But the lower bounds obtained in [SODA 2009] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for Max-Cut and Edge Dominating Set by showing that both problems 1. cannot be solved in time $f(t)n^{o(t)}$, unless Exponential Time Hypothesis (ETH) collapses; and 2. can be solved in time $n^{O(t)}$, where $f$ is an arbitrary function of $t$, on input of size $n$ and clique-width at most $t$. We obtain our lower bounds by giving non-trivial structure-preserving ``linear FPT reductions". =========================================================================== An Improved Competitive Algorithm for Reordering Buffer Management --------------------------------------------------------------------------- Authors: Noa Avigdor-Elgrabli (Technion) Yuval Rabani (Technion) Topics: Approximation Algorithms, Online problems --------------------------------------------------------------------------- We design and analyze an on-line reordering buffer management algorithm with improved $O\left(\frac{\log k}{\log\log k}\right)$ competitive ratio for non-uniform costs, where $k$ is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (ICALP 2005) giving $O(\log k)$ competitive ratio, which was also the best (off-line) approximation algorithm for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem that we introduce in this paper. =========================================================================== Deterministic Algorithms for the Lovasz Local Lemma --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Gatech) Navin Goyal (Microsoft Research, India) Bernhard Haeupler (MIT) Topics: Algorithm Analysis, Combinatorics, Distributed and Parallel Computing, Probability, Random Structures --------------------------------------------------------------------------- The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d<2^k/e k="\omega(1)" p="NP." n =" M" n =" o(2^sqrt(B))." m =" \tilde{\omega}(n^2)$." p =" NP," p="NP."> 0, unless NP has subexponential-time randomized algorithms. Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue. =========================================================================== Covering a symmetric crossing supermodular function with partition constraints --------------------------------------------------------------------------- Authors: Attila Bernáth (MTA-ELTE Egerváry Research Group, Budapest, Hungary) Roland Grappe (Laboratoire G-SCOP, Grenoble, France) Zoltán Szigeti (Laboratoire G-SCOP, Grenoble, France) Topics: Combinatorics, Graph Algorithms, Graph Theory, Optimization --------------------------------------------------------------------------- Given a symmetric crossing supermodular set function $p$ on $V$ and a partition $\mathcal{P}$ of $V$, we solve the problem of finding a graph $G=(V,E)$ having edges only between the classes of $\mathcal{P}$ such that each cut $X$ contains at least as many edges of $G$ as the function value $p(X)$. The objective is to minimize the number of edges of $G$. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jord\'an and Szigeti and the problem of covering a symmetric crossing supermodular set function solved by Bencz\'ur and Frank. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph with multipartite graph, which was earlier solved by the authors. =========================================================================== A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks --------------------------------------------------------------------------- Authors: S. M. Sadegh Tabatabaei Yazdi (Student, Texas A&M university) Serap A. Savari (Professor, Texas A&M university) Topics: Combinatorics, Information Theory, Optimization --------------------------------------------------------------------------- The linear deterministic model of relay channels is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem of Ford and Fulkerson has recently been extended to this wireless relay model. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a deterministic, polynomial-time algorithm which takes as input a single transmitted signal instead of a long block of signals. The max-flow/min-cut theorem of Ford and Fulkerson is related to a number of famous results in combinatorics including Hall's marriage theorem. Hall's marriage theorem is a special case of a well-known result in matroid theory and in transversal theory named the Rado-Hall theorem. We show that that the max-flow/min-cut theorem for linear deterministic relay networks is connected to (1) an extension of the Rado-Hall theorem applied to column-partitioned matrices into a two-dimensional transversal theorem for block matrices and (2) a combinatorial result on sequences of block matrices. =========================================================================== Vertices of Degree k in Random Maps --------------------------------------------------------------------------- Authors: Daniel Johannsen (Max-Planck-Institute for Informatics) Konstantinos Panagiotou (Max-Planck-Institute for Informatics) Topics: Combinatorics, Graph Theory, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- This work is devoted to the study of the typical structure of a random map. Maps are planar graphs embedded in the plane, and are commonly used to describe the topology of geometric arrangements. In particular, the class of all 3-connected planar maps is combinatorially equivalent to the class of all 3-dimensional convex polyhedra. Since the pioneering work of Tutte (Canadian Journal of Mathematics, 1963), maps have become very popular combinatorial objects, and in the meantime a rich theory studying various aspects of maps has evolved. However, much less is known about statistical properties of random maps, i.e., maps drawn uniformly at random from the class of all maps with a given number of edges. A major achievement in this context is the precise description of the so-called core-size of a random map, which was provided by Banderier, Flajolet, Schaeffer, and Soria (Random Structures & Algorithms, 2001). Among several other results, they showed that a random map contains typically a giant (i.e., linear-size) biconnected submap. In this work we study the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. Extending the work of Gao and Wormald (Combinatorica, 2003) on random general maps, we obtain as results of our framework precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps. =========================================================================== Bidimensionality and Kernels --------------------------------------------------------------------------- Authors: Fedor V. Fomin (Department of Informatics, University of Bergen, Norway) Daniel Lokshtanov (Department of Informatics, University of Bergen, Norway) Saket Saurabh (Department of Informatics, University of Bergen, Norway) Dimitrios M. Thilikos (Department of Mathematics, National and Kapodistrian University of Athens) Topics: Combinatorics, Graph Algorithms, Graph Theory --------------------------------------------------------------------------- Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on $H$-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of {\sl polynomial kernels} for parameterized problems. In parameterized complexity, each problem instance comes with a parameter $k$ and the parameterized problem is said to admit a {\it polynomial kernel} if there is a polynomial time algorithm, called a {\em kernelization} algorithm, that reduces the input instance to an equivalent instance (called {\em kernel}) with size bounded by a polynomial in $k$. We show that ``essentially'' all bidimensioanl problems not only have sub-exponential time algorithms and PTASs but they {\em also} have polynomial kernels, partially answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (resp. contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a quadratic kernel for classes of graphs that exclude a fixed graph (resp. an apex graph $H$) $H$ as a minor. Recently, Bodlaender et al.~[FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality and hypergraph-based combinatorial arguments, we are able to extended some of these results to minor-free and apex-minor-free graphs. Our results imply that multitude of bidimensional problems, which include {\sc Dominating Set}, {\sc Feedback vertex set}, {\sc Edge Dominating set}, {\sc Vertex Cover}, {\sc $r$-Dominating Set}, {\sc Connected Dominating Set}, {\sc Cycle Packing}, {\sc connected vertex cover}, {\sc Almost Constant Treewidth}, and many other vertex covering and packing problems, admit quadratic kernels on the corresponding graph classes. For most of these problems no polynomial kernels on $H$-minor-free graphs were know prior to our work. =========================================================================== Flow-Cut Gaps for Integer and Fractional Multiﬂows --------------------------------------------------------------------------- Authors: Chandra Chekuri (University of Illinois, Urbana-Champaign) Bruce Shepherd (McGill University) Christophe Weibel (McGill University) Topics: Graph Theory, Optimization --------------------------------------------------------------------------- Consider a routing problem instance consisting of a demand graph H=(V,E(H)) and a supply graph G=(V,E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K_{2,3}. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the "primal" method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: * Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is semi-compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a semi-compliant instance and G+H is Eulerian, then an integral routing of H exists. This result includes as a special case, routing on a ring but is not a special case of the Okamura-Seymour theorem. * Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. We also give an explicit class of routing instances that shows via elementary calculations that the flow-cut gap in series-parallel graphs is at least 2; this is motivated by and simplifies the proof by Lee and Raghavendra. * The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for some fixed constant c. * A very simple proof that the flow-cut gap is O(\log k^*) where k^* is the size of a vertex cover in H; this was previously shown by Günlük via a more intricate proof. =========================================================================== Testing monotone high-dimensional distributions --------------------------------------------------------------------------- Authors: Michal Adamaszek (University of Warwick) Artur Czumaj (University of Warwick) Christian Sohler (TU Dortmund) Topics: Property Testing --------------------------------------------------------------------------- We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite or uncountable support. Our goal is to test whether D has a given distribution or it is \epsilon-far from it (in the statistical distance, with the L_1-distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC’2005) to the case of continuous [0,1]^n cubes. We show that if a distribution D on [0,1]^n is monotone, then one can test if D is uniform with the sample complexity O(n/\epsilon^2). This result is optimal up to a polylogarithmic factor. =========================================================================== The rank of diluted random graphs --------------------------------------------------------------------------- Authors: bordenave (CNRS - Univ. Toulouse) lelarge (INRIA - ENS) Topics: Graph Algorithms, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs converging locally to a tree, we give new formulas for the asymptotic of the multiplicity of the eigenvalue $0$. In particular, the result depends only on the limiting tree structure, showing that the normalized rank is 'continuous at infinity'. Our work also gives a new formula for the mass at zero of the spectral measure of a Galton-Watson tree. Our techniques of proofs borrow ideas from analysis of algorithms, random matrix theory, statistical physics and analysis of Schr\"odinger operators on trees. =========================================================================== Utilitarian Mechanism Design for Multi-Objective Optimization --------------------------------------------------------------------------- Authors: Fabrizio Grandoni (Universita di Roma Tor Vergata) Piotr Krysta (University of Liverpool) Stefano Leonardi (Sapienza Universita di Roma) Carmine Ventre (University of Liverpool) Topics: Approximation Algorithms, Economics, Game Theory, Internet and Network Algorithms, Mechanism Design, Optimization --------------------------------------------------------------------------- In a classic optimization problem the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems. In this setting we are given a main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multiobjective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our construction also applies to multi-dimensional knapsack and multi-unit combinatorial auctions. Our FPTASs compute a (1 + epsilon)-approximate solution violating each budget constraint by a factor (1 + epsilon). For the case of (non-perfect) matchings we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest edges in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time in a way similar to the smoothed analysis of algorithms). All the mentioned results match the best known approximation ratios, which are however obtained by non-truthful algorithms. =========================================================================== Property Testing and Parameter Testing for Permutations --------------------------------------------------------------------------- Authors: Carlos Hoppen (IME, USP, São Paulo, Brazil) Yoshiharu Kohayakawa (IME, USP, São Paulo, Brazil) Carlos G. T. de A. Moreira (IMPA, Rio de Janeiro, Brazil) Rudini M. Sampaio (DC, UFC, Fortaleza, Brazil) Topics: Combinatorics, Probability, Property Testing, Random Structures, Sublinear Algorithms --------------------------------------------------------------------------- There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations. We give a permutation counterpart of a famous result by Alon and Shapira stating that every monotone graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in $[0,1]^2$, which in turn may be used to define a new model of random permutations. =========================================================================== Monotonicity in Bargaining Networks --------------------------------------------------------------------------- Authors: Yossi Azar Nikhil Devanur Kamal Jain Yuval Rabani Topics: Algorithm Analysis, Economics, Game Theory --------------------------------------------------------------------------- We study bargaining networks, discussed in a recent paper of Kleinberg and Tardos \cite{KT}, from the perspective of cooperative game theory. In particular we examine two solution concepts, the nucleolus and the core center. Both solution concepts define unique solutions, so they provide testable predictions. In general coalitional games, both solutions are weakly monotone, but they are not strongly monotone. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that both the nucleolus and the core center satisfy this monotonicity property. Our proofs are based on a primal-dual argument (for the nucleolus) and on the FKG inequality (for the core center). We further observe some qualitative differences between the two solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center satisfies it. On the other hand, the nucleolus is easy to compute, whereas computing the core center is \#P-hard (yet it can be approximated in polynomial time). =========================================================================== A Lower Bound for Succinct Rank Queries --------------------------------------------------------------------------- Authors: Mihai Patrascu (AT&T Labs) Topics: Complexity, Compression, Data Structures, Information Theory --------------------------------------------------------------------------- The rank problem in succinct data structures is to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form rank(k) = Sum_{i=1..k} A[i]. The problem has been intensely studied, and features as a subroutine in a majority of succinct data structures. We show that in the cell probe model with w-bit cells, if rank takes t time, the space of the data structure must be at least n + n/w^O(t) bits. This redundancy/query trade-off is essentially optimal, matching our upper bound from [FOCS'08]. =========================================================================== Amplified Hardness of Approximation for VCG-Based Mechanisms --------------------------------------------------------------------------- Authors: Shaddin Dughmi (Stanford University) Hu Fu (Cornell University) Robert Kleinberg (Cornell University) Topics: Approximation Algorithms, Complexity, Economics, Game Theory, Mechanism Design --------------------------------------------------------------------------- If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an approximation factor better than 1/2. Moreover, for the k-player version of the same problem, the hardness of approximation improves to 1/k under the same two-player hardness assumption. (We note that 1/k is achievable by a trivial deterministic maximal-in-range mechanism.) This hardness result encompasses not only deterministic maximal-in-range mechanisms, but also all universally-truthful randomized maximal in range algorithms, as well as a class of strictly more powerful truthful-in-expectation randomized mechanisms recently introduced by Dobzinski and Dughmi. Our result applies to any class of valuation functions that satisfies some minimal closure properties. These properties are satisfied by the valuation functions in all well-studied APX-hard social welfare maximization problems, such as coverage, submodular, and subadditive valuations. We also prove a stronger result for universally-truthful maximal-in-range mechanisms. Namely, even for the class of budgeted additive valuations, which admits an FPTAS, no such mechanism can achieve an approximation factor better than 1/k in polynomial time. =========================================================================== On the possibility of faster SAT algorithms --------------------------------------------------------------------------- Authors: Mihai Patrascu (IBM Almaden) Ryan Williams (Institute for Advanced Study) Topics: Complexity, Geometry, Graph Algorithms --------------------------------------------------------------------------- We investigate the prospects for an algorithm for Boolean CNF satisfiability (CNF-SAT) that runs in $O^*(2^{\delta n})$ time for some $\delta < d =" \Omega(\log"> \log n$. In particular, since the hypercube has strong local expansion properties, (ii) and (iii) imply that RW-MARK and RW-R-RANK mark whp all nodes of an n-node hypercube in $O(n)$ steps. More generally, our results imply that on many important graph classes, random walks which are allowed to mark (cover) neighbors, have the same cover time as the corresponding centralized coupon collecting process. =========================================================================== A Model of Computation for MapReduce --------------------------------------------------------------------------- Authors: Howard Karloff (AT&T Labs) Siddharth Suri (Yahoo! Research) Sergei Vassilvitskii (Yahoo! Research) Topics: Distributed and Parallel Computing, Internet and Network Algorithms --------------------------------------------------------------------------- In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on the terabyte and petabyte scales. Used daily at companies such Yahoo!, Google, Amazon, and Facebook and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines. One key feature of MapReduce that diﬀerentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation. We propose a model of eﬃcient computation using the MapReduce paradigm. Our model allows each machine to perform sequential computations in time polynomial in the size of the input that machine receives. Moreover, since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be (substantially) sublinear in the size of the input. We compare MapReduce to the PRAM model of computation. We prove a simulation lemma showing that a large class of PRAM algorithms can be eﬃciently simulated via MapReduce. The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation. We show how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to O(log(n)) rounds needed by a standard PRAM. We also show to evaluate a wide class of functions using the MapReduce framework. We conclude by applying this result to show how to compute many basic algorithmic problems such as undirected connectivity in the MapReduce framework. =========================================================================== Fast SDP Algorithms for Constraint Satisfaction Problems --------------------------------------------------------------------------- Authors: David Steurer (Princeton University) Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization, Probability --------------------------------------------------------------------------- The class of constraint satisfactions problems (CSPs) contains many fundamental combinatorial optimization problems such as MaxCut and Max3SAT. Recently, Raghavendra (STOC`08) showed that a certain semidefinite programming relaxation gives the best possible approximation for any CSP, assuming Khot's Unique Games Conjecture. Raghavendra and Steurer (FOCS`09) show that independent of the truth of the Unique Games Conjecture the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities. We present an algorithm that finds an approximate solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS`09) yields an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture Our algorithm employs a framework of Arora and Kale (STOC`07) for solving semidefinite programs. In this framework, the crucial step is to design an efficient width-bounded separation oracle. We show how to implement this oracle by solving a sequence of local linear programs. We also generalize the framework of Arora and Kale in order to deal with irregular instances more efficiently. =========================================================================== Lower bounds for Edit Distance and Product Metrics via Poincare-Type Inequalities --------------------------------------------------------------------------- Authors: Alexandr Andoni (MIT) T.S. Jayram (IBM Almaden) Mihai Patrascu (IBM Almaden) Topics: Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings' length) communication complexity. This is an exponential improvement over the previous, doubly-logarithmic, lower bound of [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over non-repetitive strings). In this special case, it is polynomially related to the recent upper bound of [Andoni-Indyk-Krauthgamer, SODA'09]. From a technical perspective, we prove a direct-sum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the max-product metric \ell_\infty^d(X) requires \Omega(d) bits. The conclusion, in fact, also holds for arbitrary two-way communication. The proof uses a novel technique for information complexity based on Poincar\'e inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity. =========================================================================== Shape Replication Through Self-Assembly and RNase Enzymes --------------------------------------------------------------------------- Authors: Zachary Abel (Harvard University) Nadia Benbernou (Massachusetts Institute of Technology) Mirela Damian (Villanova University) Erik Demaine (Massachusetts Institute of Technology) Robin Flatland (Siena College) Skott Kominers (Harvard University) Robert Schweller (University of Texas Pan American) Martin Demaine (Massachusetts Institute of Technology) Topics: Bioinformatics, Geometry --------------------------------------------------------------------------- We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus 0 shapes can be replicated infinitely many times with O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using either O(log n) stages or O(log n) tile types. =========================================================================== Universal $\epsilon$-approximators for integrals --------------------------------------------------------------------------- Authors: Michael Langberg (The Open University of Israel) Leonard J. Schulman (Caltech) Topics: Geometry, Learning --------------------------------------------------------------------------- Let $X$ be a space and $F$ a family of ${0,1}$-valued functions on $X$. Vapnik and Chervonenkis showed that if $F$ is "simple" (finite VC dimension), then for every probability measure $\mu$ on $X$ and $\e>0$ there is a finite set $S$ such that for all $f \in F$, $\sum_{x \in S} f(x)/|S| = [\int f(x) d\mu(x)] \pm \e$. Think of $S$ as a "universal $\epsilon$-approximator" for integration in $F$. $S$ can actually be obtained w.h.p. just by sampling a few points from $\mu$. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., $[0,1]$-valued) real functions. In this work we establish similar "universal $\epsilon$-approximators" for families of unbounded nonnegative real functions --- in particular, for the families over which one optimizes when performing data classification. In this case the $\epsilon$-approximation is multiplicative. =========================================================================== A 1.4-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model --------------------------------------------------------------------------- Authors: Bahman Bahmani (Stanford University) Aranyak Mehta (Google, Inc.) Rajeev Motwani (Stanford University) Topics: Algorithm Analysis, Graph Algorithms, Online problems --------------------------------------------------------------------------- A classic theorem by Vizing proves that if the maximum degree of a graph is $\Delta$, then it is possible to color its edges, in polynomial time, using at most $\Delta+1$ colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. Here, a natural model is that edges arrive online, but in a random permutation. Even in the random permutations model, the best known analysis for any algorithm is factor 2, which comes from the simple greedy algorithm (which is factor 2 even in the worst case online model). The algorithm of Aggarwal et al. (FOCS 03) provides a 1+o(1) factor algorithm, but for the case of multigraphs, when $\Delta = \Omega(n^2)$, where $n$ is the number of vertices. In this paper, we show that for graphs with $\Delta = \Omega(polylog(n))$, it is possible to color the graph with $1.4\Delta+o(\Delta)$ colors in the online random order model. Our algorithm is inspired by a 1.6 factor distributed offline algorithm of Panconesi and Srinivasan (SICOMP'97), which we extend by reusing colors online in multiple rounds. =========================================================================== Orthogonal Ham-Sandwich Theorem in R3 --------------------------------------------------------------------------- Authors: Sergey Bereg (University of Texas at Dallas) Topics: Geometry, Topological Problems --------------------------------------------------------------------------- The ham-sandwich theorem states that, given $d\ge 2$ measures in $\R^d$, it is possible to divide all of them in half with a single $(d-1)$-dimensional hyperplane. We study an orthogonal version of the ham-sandwich theorem and define an orthogonal cut using at most $d$ hyperplanes orthogonal to coordinate axes. For example, a hyperplane orthogonal to a coordinate axis is an orthogonal cut. We prove that any three measures in $\R^3$ can be divided in half each with a single orthogonal cut. Applied to point measures, it implies that any three finite sets of points in $\R^3$ can be simultaneously bisected by an orthogonal cut. We present an algorithm for computing an orthogonal ham-sandwich cut in $O(n\log n)$ time. =========================================================================== Bounding Variance and Expectation of Longest Path Length in DAGs from Variance and Expectation of Edge Lengths --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Supratik Chakraborty (Indian Institute of Technology Bombay) Topics: Graph Algorithms, Probability --------------------------------------------------------------------------- We consider the problem of computing bounds on the variance and expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We focus primarily on the case where all edge lengths are non-negative and the DAG has a single source and sink node. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG structures. Our algorithm is motivated by an analogy with balance of forces in a network of "strange" springs. We present some experimental results showing the effectiveness of this algorithm for computing bounds in variance and expectation of circuit delays from variance and expectation of gate delays

اٍے حسن حقیقی نُور اذل

2009-08-19T15:52:00.003-04:00

اٍے حسن حقیقی نُور اذل۔۔۔۔
تینوں واجب تے امکان کہوں

تینوں خالق ذات قدیم کہوں
تینوں حادث خلق جہان کہوں

تینوں مطلق محض وجود کہوں
تینوں علمیہ اعیان کہوں۔۔۔۔

ارواح نفوس عقول مثال
اشباح عیان نہان کہوں

تینوں عین حقیقت ماہیت
تینوں عرض صفت تے شان کہوں

انواع کہوں اوضاع کہوں
اطوار کہوں اوذان کہوں۔۔

تینوں عرش کہوں افلاک کہوں
تینوں ناذ نعیم جنان کہوں۔۔۔۔

تینوں تَت جماد نبات کہوں
حیوان کہوں انسان کہوں

تینوں مسجد مندر دیر کہوں
تینوں پوتھی تے قرآن کہوں

تسبیح کہوں زنار کہوں
تینوں کفر کہوں ایمان کہوں

تینوں بادل برکھا گاج کہوں
تینوں بجلی تے باران کہوں

تینوں آب کہوں تے خاک کہوں
تینوں باد کہوں نیران کہوں

تینوں دسرت لچھمن رام کہوں
تینوں سیتا جی جانان کہوں

بلدیو جسودا نند کہوں
تینوں کشن کنیھا کان کہوں

تینوں برما بشن گنیش کہوں
مہادیو کہوں بھگوان کہوں

تینوں گیت گرنتھ تے بید کہوں
تینوں گیاں کہوں اگیاں کہوں

تینوں آدم حوا شیت کہوں
تینوں نوح کہوں طوفان کہوں

تینوں ابراہیم خلیل کہوں
تینوں موسیَ بن عمران کہوں

تینوں ہر دل دا دلدار کہوں
تینوں احمد عالی شان کہوں

تینوں شاہد ملک حجاز کہوں
تینوں باعث کون مکان کہوں

تینوں ناز کہوں انداز کہوں
تینوں حور پری غلمان کہوں

تینوں نوک کہوں تینوں ٹوک کہوں
تینوں سرخی بیڑا پان کہوں۔۔۔۔۔۔

تینوں طبلہ تے طنبور کہوں۔۔
تینوں ڈھولک تے سر بان کہوں

تینوں حسن تے ہار سنگھار کہوں
تینوں عشوہ غمزہ آن کہوں۔۔۔۔

تینوں عشق کہوں تینوں علم کہوں
تینوں وہم یقین گمان کہوں۔۔۔۔۔۔۔

تینوں حسن قوی ادراک کہوں
تینوں ذوق کہوں وجدان کہوں

تینوں سکر کہوں سکران کہوں
تینوں حیرت تے حیران کہوں

تسلیم کہوں تلوین کہوں
تمکین کہوں عرفان کہوں

تینوں سنبل سوسن سرو کہوں
تینوں نرگس نافرمان کہوں

تینوں لالہ داغ تے باغ کہوں
گلزار کہوں بستان کہوں

تینوں خنجر تیر تفنگ کہوں
تینوں برچھا بانک سنان کہوں

تینوں تیر خدنگ کمان کہوں
سوفار کہوں پیکان کہوں

بے رنگ کہوں بے مثل کہوں
بے صورت ہر ہر آن کہوں

سبوح کہوں قدوس کہوں
رحمان کہوں سبحان کہوں

کر توبہ ترت فرید سدا
ہر شے نوں پر نقصان کہوں

اسے پاک الکھ بے عیب کہوں
اسے حق بے نام نشان کہوں

خواجہ غلام فرید۔۔