Special entry for you, my friend
Happy New Year and all that. Recently I got back from a two-week journey to India (to attend the QIP conference in New Delhi and, of course, liveblog from the Taj) as well as England (to meet up with family in London and make a religious pilgrimage to Bletchley Park).
Even though my travel entries typically get fewer comments than anything else, I nonetheless feel a historic responsibility to record my first visit to a subcontinent with one-sixth of the world’s population — the birthplace not only of my adviser and so many other great theoretical computer scientists, but also of Gandhi, Ramanujan, the Buddha, and commenter Nagesh Adluru. But where do I even start? Writing anything open-ended has always been a chore for me, and it’s only getting harder with time.
So I’ll tell you what: I’ll just post some photos with commentary. Then ask me whatever you want in the comments section: “Were there any good talks at QIP?” “Were you brave enough to sample the strange, exotic North Indian dishes, like ‘naan’ and ‘samosas’ and ‘chicken curry’?” “Having spent a full week in India, to what extent, if any, do you think the Bhutto assassination will destabilize Indo-Pakistani relations?”
India: where every imaginable entity with wheels, feet, or hooves can be found on the road, making deafening noises while swerving to kill you; the water’s not even safe for toothbrushing; the beggars have their own beggars; and the cellphone network is more reliable than anything in the US.
These are students and religious pilgrims at the Dayalbagh colony near Agra, the headquarters of one branch of the Radha Soami sect of Hinduism. They’re laboring in the fields at dawn, before coming in to hear me and others give quantum computing talks. I’m not making this up.
When I agreed to give a talk at the Dayalbagh Educational Institute, all I knew about my hosts is that they were computer scientists near Agra who would take me on a guided tour of the Taj Mahal and arrange the logistics. I had no idea that my hosts — and their self-supporting agricultural commune of about 20,000 people, led by religious scholars fascinated by quantum computing theory — would turn out to be considerably more interesting than the Taj itself.
For my talk, I was going to present some recent results with Peter Shor, Salman Beigi, and Bill Fefferman on the complexity class QMA(k) (Quantum Merlin-Arthur with multiple unentangled Merlins). But then I learned that over 200 people would be attending. I panicked: “there aren’t 200 people on Earth who would care about this talk, let alone 200 people on a Hindu kibbutz near Agra!” So I quickly substituted my usual dog-and-polynomial show about the limits of quantum computers.
I was surprised that the guru of the sect, Prof. P. S. Satsangi, actually came to my talk. Everyone stood at attention when he entered the room, and then he sat in a special chair surrounded by flowers at the front of the lecture hall. He did not ask questions.
In the end, while I couldn’t assent to the Radha Soamis’ mystical beliefs (as they were explained to me), I found much in their way of life to recommend it. I had fun imagining, say, a Kansas farmtown where a quantum computing workshop would be a major public event, attended by the mayor and every local dignitary.
This is where I stayed in New Delhi: at the Islamic Cultural Centre Guest House. I chose to stay here because (1) as someone who’s occasionally blogged about the Israeli/Palestinian conflict, I felt a historic responsibility to make a bold peace gesture, and (2) it was the only place in walking distance to the conference center.
As you can see from the Christmas tree out in front, the Islamic Centre was happily not averse to ecumenicism. As explained to me by my “friend” at the guest house (the guy who knocked on my door every fifteen minutes to see if I needed anything, before asking me for a tip), “here in India there is no ‘you Hindu, you Muslim, you Buddhist, you Sikh.’ All are brothers, you understand? Tip?”
Dorit Aharonov and Barbara Terhal passionately debating some adiabatic something-or-other near the Qutb Minar, a twelfth-century minaret.
Need Grover’s algorithm tailored to solve the element distinctness problem in n2/3 queries? I know just the guy for such jobs…
If you can’t read it, the sign says “MADHUSUDAN MOTORS.”
Our guides: “c’mon, move along, nothing to see here … just a stray monkey …”
The obligatory photo. Not Photoshopped, I promise.
Here we shift the scene from India to its former colonialist ruler (now a quaint, scone-intensive island in the North Atlantic). I’m standing in front of the Bletchley Park mansion, an hour and a half by train from London. In the early nineties, this site was apparently going to be demolished to make way for housing developments. Then someone pointed out that, by current estimates, the cryptanalysis done at Bletchley Park probably shortened World War II by at least two years and saved about twenty million lives. So they made it into a museum. Next time you’re in London, I strongly recommend making the pilgrimage (just beware that the place closes at 4PM).
This is a Bombe.
Alan Turing’s office in Hut 8.
Follow
Comment #1 January 3rd, 2008 at 6:40 pm
i figure the not photoshopped promise was in reference to the Taj, right? cause your picture at Bletchley looks suspiciously similar to the wikipedia photo… of course im not serious. i cant think of any good questions yet though.
Comment #2 January 3rd, 2008 at 7:18 pm
So, how were the talks at QIP?
Comment #3 January 3rd, 2008 at 7:28 pm
Next time you’re in London could you stop by to give us a talk at Imperial or UCL?
Comment #4 January 3rd, 2008 at 8:20 pm
Marc: Sorry, it was bad timing (over Christmas)! I gave a talk at Imperial in 2002, and would love to do so again the next time I’m in London.
Comment #5 January 3rd, 2008 at 8:45 pm
What talks caught your attention, Scott? More importantly, what was your favorite north Indian dish? 🙂
Awesome pic of Turing’s office. Bletchley must have been quite the experience.
Comment #6 January 3rd, 2008 at 9:00 pm
Ashton: The talks were good! I could discern at least two recurring themes this year:
(1) Falsification of conjectures that would’ve made life easier were they true. Cubitt et al. falsified the additivity of “minimum output p-Renyi entropy” for p close to 0. Patrick Hayden falsified the same conjecture for p>1. (The p=1 case is the famous Additivity Conjecture; we now know that if it holds, it can’t be as a consequence of a more general statement for all p.) Ji et al. falsified the “LU-LC conjecture,” that any two stabilizer states that are locally equivalent are equivalent under local stabilizer operations. (Their counterexample requires 29 qubits!)
(2) Dealing with entanglement in multi-prover interactive proof systems. Kempe, Kobayashi, Matsumoto, Toner, and Vidick showed (roughly speaking) that even if three suspects in separate interrogation rooms use entanglement to secretly coordinate their answers, the police can still catch them lying with 1/exp(n) probability. Ito et al. showed this is true even if each suspect outputs only a single bit. On the other hand, Kempe, Regev, and Toner showed that the “unique games conjecture” with entangled provers is false. Navascues, Pironio, and Acin showed that if the suspects in the separate interrogation rooms never need more than finitely many EPR pairs, then their optimal strategy is computable (sounds obvious but isn’t!). Strangest of all, Kempe, Kobayashi, Matsumoto, and Vidick (you can see why I couldn’t use “et al.” before…) gave evidence that if the suspects in separate interrogation rooms are entangled, that sometimes helps them prove their innocence.
I also liked the invited talks by Michael Wolf, who gave examples of N-dimensional superoperators that can’t be decomposed as products of two other N-dimensional superoperators unless one of them is unitary; Oded Regev, who (jointly with Ben-Aroya and de Wolf) gave a “direct product” version of the ANTV dense quantum coding lower bound; and Falk Unger, who gave new upper bounds on the fault-tolerance threshold (i.e., the decoherence rate above which quantum computing is impossible).
Here’s the program. I’m sure I forgot a great deal — so whoever else was there, fill in what I missed!
Comment #7 January 3rd, 2008 at 9:20 pm
Bilal: The best food I had in India was actually at the Dayalbagh colony (they grow everything on the premises). It was all vegetarian, but unfortunately I don’t know what any of it was called. There was one thing sort of like falafels, and another thing involving paneer, and soup, and probably yogurt, and the best damn oranges I ever had.
Comment #8 January 4th, 2008 at 1:15 am
Hi Scott,
Of the topic, GI in P ???
http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.0398v1.pdf
any comments on this recent paper on the arxiv.
Comment #9 January 4th, 2008 at 1:41 am
Ghaith, there are many, many papers on the arXiv claiming to prove GI is in P (or P=NP, or P≠NP, or NP is in BQP…). If I read all such papers, then I wouldn’t have time for anything else. It’s an interesting question how you decide whether a given paper crosses the plausibility threshold or not. For me personally, the AKS “PRIMES in P” paper somehow crossed it whereas this one somehow doesn’t.
Of course, I’d welcome an opinion from anyone who’s actually read the paper.
Comment #10 January 4th, 2008 at 3:00 am
The GIP paper seems legit.
Comment #11 January 4th, 2008 at 4:35 am
Dear Brother
It was very pleasing to read that Dr. Prem Saran Satsangi, the Guru of Radhasoami sect of Agra has visited personally to attend your lecture.
The theories and principles of Radhasoami sect have stood the test of last 200 years time.
Dr.Prem Saran Satsangi is a renowned physicist and has served INDAIN INSTITUTE OF TECHNOLOGY, DELHI, INDIA.
Anil Sadevra
Kampala, Uganda
Comment #12 January 4th, 2008 at 5:10 am
“quaint, scone-intensive island in the North Atlantic”
That description deserves to be in tourist brochures.
Comment #13 January 4th, 2008 at 7:12 am
After a first quick reading I didn’t spot anything obviously wrong in the GIP-paper. The author seems to be a serious mathematician too.
Comment #14 January 4th, 2008 at 10:03 am
scott, your succinct description of india following the pic of the elephant, is better than what many of us who think we understand the subcontinent can come up with! and an aside — i think i was unclear in a comment/request last month — my question was whether the lecture notes from your spring ’08 course at mit will be available on the web, just as Democritus. thanks, and wish you a happy new year.
Comment #15 January 4th, 2008 at 10:19 am
Thanks, Aravind, and happy new year to you too! Yes, we’ll try to make either slides or lecture notes available for Great Ideas In Theoretical Computer Science. (Though after the Democritus democle I’m hesitant to promise anything… 🙂 )
Comment #16 January 4th, 2008 at 1:16 pm
The GI in P result looks good to me too. Basically, there are three steps:
(1) Rephrase GI as an integer programming problem in polynomially many variables. (No big surprise, traveling salesman and three-colorability are also integer programming problems.)
(2) Show that the polytope associated to the integer programming problem has polynomially many facets. (This distinguishes us from the travelling salesman case.)
(3) Show that the integer programming problem is equivalent to its linear relaxation. (This distinguishes us from the three coloring case.)
In both parts 2 and 3, the point is that the polytope “acts like” the Birkhoff polytope. I think I’ll pull together a slightly longer blog post about this, if someone else hasn’t written one already.
Comment #17 January 4th, 2008 at 1:39 pm
On the other hand, I see that the author has put up a new version where he retracts his claim, saying that the argument in part (2) was broken. It would be interesting to find some facets of the polytope other than the ones he lists.
Comment #18 January 4th, 2008 at 2:23 pm
I guess being willing to retract a claim after an error has been found is what distinguishes a serious mathematician from an arxiv-nut.
Comment #19 January 4th, 2008 at 2:27 pm
I guess being willing to retract a claim after an error has been found is what distinguishes a serious mathematician from an arxiv-nut.
Yes. 🙂
Comment #20 January 4th, 2008 at 3:53 pm
Hi Scott,
A small clarification of your comment 6(1): our paper that was presented at QIP (arXiv:0712.3628) only deals with disproving the minimum output Renyi p-entropy additivity conjecture for p close to 0. Patrick’s paper (arXiv:0707.3291) disproves the same conjecture for p>1. This conjecture was previously disproven for p>2 by Andreas Winter and previously still by Holevo and Werner for p>4.79 (!).
And of course, the only value of p that we really care about is actually p=1…
Comment #21 January 4th, 2008 at 4:07 pm
Thanks, Ashley! I took the liberty of correcting my comment.
Comment #22 January 4th, 2008 at 4:38 pm
Tell us why you recommend their way of life. Sounds interesting; many scientists over the years have said that the places they do their best work are often enveloped in nature.
Also, is this “Great Theoretical Ideas of Computer Science” course similar to the course with the same title at CMU? I’ll be TAing the CMU course in the coming semester and will be interested to compare/contrast the slides and problem sets. 🙂
Comment #23 January 4th, 2008 at 4:55 pm
Matt: I don’t know if I recommend their way of life; I just think it clearly has something going for it. They basically have a small self-sustaining farming village that’s led by academics (!) and that holds the life of the mind in extremely high esteem. I can’t think of anything else like that in history, except maybe for certain kibbutzim, or certain failed socialist communes, or the shtetls of pre-Holocaust Europe. (Anyone know of other examples?)
My course — “Great Ideas In Theoretical Computer Science” — has nothing at all to do with CMU’s, which as you know is called “Great Theoretical Ideas In Computer Science.” In designing my course, I drew no inspiration whatsoever from Steve Rudich and his course of a completely different name.
Comment #24 January 4th, 2008 at 5:07 pm
Scott: erm, you might want to take the liberty of changing the ≥ to a > too 😉
Comment #25 January 4th, 2008 at 5:34 pm
Duhhhhh
Thanks
Comment #26 January 4th, 2008 at 8:32 pm
Scott, Thanks for mentioning me in the post.
I am curious to know why you chose that title for the post.
Comment #27 January 4th, 2008 at 9:08 pm
Nagesh: Sorry, bad attempt at humor. In Delhi, people who wanted me to buy something or tip them were constantly referring to me as their friend.
Comment #28 January 5th, 2008 at 12:38 am
Oh now it makes sense:)
Comment #29 January 5th, 2008 at 12:45 am
That’s ok, i too am guilty of paying people to say that they’re my friends. There’s no shame in being a friend-payer. 🙂
Comment #30 January 5th, 2008 at 3:21 pm
Thanks for the Turing Office touring snapshots.
What would he say (as pioneer of modern cryptography), what would Claude Shannon say, and what would you say (other than a well-deserved joke about the title) about:
arXiv:0801.0253 [pdf, other]
Title: Toward a statistical mechanics of four letter words
Authors: Greg J. Stephens, William Bialek
Subjects: Neurons and Cognition (q-bio.NC); Computation and Language (cs.CL); Data Analysis, Statistics and Probability (physics.data-an); Physics and Society (physics.soc-ph)
We consider words as a network of interacting letters, and approximate the probability distribution of states taken on by this network. Despite the intuition that the rules of English spelling are highly combinatorial (and arbitrary), we find that maximum entropy models consistent with pairwise correlations among letters provide a surprisingly good approximation to the full statistics of four letter words, capturing ~92% of the multi-information among letters and even “discovering” real words that were not represented in the data from which the pairwise correlations were estimated. The maximum entropy model defines an energy landscape on the space of possible words, and local minima in this landscape account for nearly two-thirds of words used in written English.
Comment #31 January 5th, 2008 at 9:04 pm
I don’t know if I recommend their way of life; I just think it clearly has something going for it. They basically have a small self-sustaining farming village that’s led by academics (!) and that holds the life of the mind in extremely high esteem.
Since ancient times, intellectuals have held a high position in Hindu society. I think it was Swami Vivekananda who said that the Indian caste system is preferable to the European feudal system in that sages, ascetics and philosophers, instead of landowners, hedonists and despots, are (theoretically at least) on top of the societal heap.
Of course, the problem with most such setups is that the determination of who is the leader comes to be determined more by heredity than by merit. Do you know any details about how the leader of the Radhasoami sect is chosen?
Comment #32 January 5th, 2008 at 10:24 pm
arnab: I asked them how the leader is chosen, but I didn’t completely understand the answer. They said they have a community meeting, and the leader is chosen there by “universal acclamation” (which I guess means discussing likely candidates until a consensus is reached). It sounded a bit like the selection of a pope by the College of Cardinals.
I note from the Wikipedia article that, as one might predict given this succession model, the movement has split several times in its history.
Comment #33 January 7th, 2008 at 7:12 am
The leader (`Huzoor’) is usually designated by the outgoing Huzoor. So in a way this is similar to the papal succession except that the incoming pope is indicated by the outgoing. The incumbent Huzoor usually comes to a decision about this matter at some point in his life, when he is convinced that it’d be wise to do so.
Sorry if that sounds a bit too crypto-mystical, but not being Radha Soami myself, I am providing an approximation based on what I’ve gleaned from my mother’s descriptions (she’s Radha Soami).
There was a dispute about the `succession’ once before and it lead to the formation of an independent group.
–Sanatan
Comment #34 January 7th, 2008 at 4:08 pm
Excellent blog entry. I especially liked the picture of the commune workers, and the story behind it. Maybe you could start your own transcendentalists commune in Concord MA.
Comment #35 January 8th, 2008 at 3:58 pm
With regards to the Navascues, Pironio, and Acin result in QIP 2008, did the authors mention a more recent draft of their work? All I could find is
http://arxiv.org/abs/quant-ph/0607119
— something a little old to appear in QIP 2008. In that paper, the authors mention a “future paper” that I can’t seem to track down.
Gus
Comment #36 January 14th, 2008 at 1:25 am
Welcome to RS Dayalbagh…in response to your question about how the new true Guru (Satguru) is chosen…we
receive hints during the Predecessor’s lifetime and after..both external and internal…based on our own capacities and abilities…and these lead us to our new Guru…the source of divinity is the same…almost like the Trinity…the same Holy Spirit Current from the Lord inspires the new Guru…so, there is a change of physical frame, but the Guru…is ever the same…I hope this helps…it sounds like you had a very special time in the fields of Dayalbagh. Radhasoami…
Comment #37 January 14th, 2008 at 1:32 am
Oh, and I wanted to add…there is also a General Body
Meeting where last time 25,000 or so attended and Dr. Satsangi was acclaimed…but, many had already received
internal hints that He was our new Guru…often these hints
come in the form of dreams or premonitions…and it was the
same in Dr. Satsangi’s Predecessor’s time (Dr. Lal Sahib), though clear instructions were given for Dr. Lal Sahib’s Predecessor, His Holiness Mehta Sahib, by His Predecessor,
Sir Anand Swarup (Founder of Dayalbagh and Knighted for
His accomplishments).
Comment #38 January 15th, 2008 at 7:57 pm
Dear Scott,
I want an opinion about something which bothers me.
Can you become a good/successful scientist , if you are not gifted as you and some people who interact on this blog with you.
Can you become a good scientist by just sheer hard work.
I want your opinion.
thanks,
b
Comment #39 January 15th, 2008 at 9:59 pm
I think pretty much every good scientist puts in a lot of hard work, no matter how much they try to make it look easy. But I think it is like playing a sport at a professional level or playing a musical instrument professionally: the work has to be focused practice, with the aim of getting better. You can’t just idly read stuff. Instead, the goal has to be to make the science you are working in “natural” to you, just as natural as speaking your native language. Work out toy problems, go through the steps of papers, always try to figure out the easy way to do things. If it doesn’t become natural, then something’s wrong.
But by “it”, I think there are many ways one can be a good scientist. I mostly do simple analytical calculations. One of my colleagues does almost exclusively numerical simulations, and almost never picks up a pen. He still is one of the best scientists I know, because he has a good grasp on the physics of what is going on. I’ve known other scientists who had much stronger analytic skills but weren’t as good as this guy. Different approaches.
By the way, is physics the only field that has a phrase of the form “the physics of the problem”? Meaning, the important terms or effects, an understanding of what to keep and what to drop. Sort of the same as “intuition”, but not really. Computer scientists don’t talk about understanding the “computer science” of the problem…
Comment #40 January 16th, 2008 at 12:47 am
They talk about understanding the “complexity” of the problem… That’s in the ballpark.
Comment #41 January 16th, 2008 at 1:45 am
I think either gift or hard work alone is the necessary condition for becoming a good scientist.
Both of them are the sufficient and necessary conditions for becoming a good scientist.
I can only work hard so I gave up be a good scientist or even a scientist.
Comment #42 January 16th, 2008 at 2:18 am
Why not just do as you feel and see what comes of it? Whether you are gifted is not your decision.
Comment #43 January 16th, 2008 at 2:29 am
There’s no gifted machines among Turing machines. There’s only fancy tapes and stuff..
Comment #44 January 16th, 2008 at 2:39 am
We’re all mathematically equivalent…
Comment #45 January 16th, 2008 at 4:56 am
Yes, giving it a try does no harm. You should come to a point where you know whether you still have the motivation/ability/passion to go on.
Comment #46 January 16th, 2008 at 11:04 am
All good things should reduce to dishes and detergent. This way we wouldn’t be able to get around not doing them.
Comment #47 January 16th, 2008 at 6:00 pm
Scott: All I would like to say that you are very lucky; nothing better one can expect in one’s life; you got the Best ever dreamt divine gift: Gracious Huzure Dr. Prem Saran Satsangi
‘s presence in your lecture; Gracious Huzur Dr. Satsangi Sahib Blessed you with His presence. You are very fortunate!!!; there must be something special about you. You said that He (DR. P. N. Satangi Sahib) does not ask any questions; because he has all the answers.
Comment #48 January 17th, 2008 at 7:48 pm
Thanks Matt and other for the inputs.
May be others can chip in.
Comment #49 February 12th, 2008 at 10:29 pm
Scott,
I/We as Indians dont find anything strange about the Indian food – Naan, samosa etc. It is always frustrating whenever westerners call it strange, i would like to think we are much better (if not the best) in culinary tastes when compared to the rest of the world. Instead i would like to see westerners comment on Indian food as being far more nuanced and finessed as opposed to the bland and just throw it on fire western (American) food.
It is well experimented cuisine wherein women folk have tried and tired and figured out the so many varieties both in terms of taste and form..
Comment #50 February 12th, 2008 at 11:52 pm
Arun, it’s called sarcasm. Far from being strange to me, naan and samosas are among the staples of my diet.