Shtetl-Optimized

I’m normally loath to announce conferences on this blog, but my friend Michael Vassar has made an offer that appeals to my vanity, desire to please, and most of all legendary business sense.  Here it is: anyone who registers for the upcoming Singularity Summit, October 3-4 in New York, can get 50% off the registration fee by mentioning this blog.

Topics on the agenda will include (I assume) the technical prospects for immortality, brain-uploading, superintelligent AIs, and the transformation of all matter in the universe into sentient computronium.  (In other words, none of that loony stuff we discuss at CS conferences, Merlin-Arthur and whatnot.)

Speakers will include Ray Kurzweil, Michael Nielsen, Robin Hanson, Eliezer Yudkowsky, David Chalmers, and several others familiar in these parts of the nerdosphere.

I’ve never been to one of these Singular shindigs before, and unfortunately can’t make this one (I’ll be visiting UC Santa Barbara and the University of Washington).  But regular readers will know that I enjoy talking with Transhumanists and Singulatarians—even if I don’t exactly share their urgency about the coming robot revolution, and worry more about the superdoofosities of today than the superintelligences of tomorrow.  I’m sure that, for some readers, the very fact that I’m willing to debate people who consider me crazy for not arranging to have my brain frozen in liquid nitrogen when I die—or that I’d advertise a conference for such people—makes me almost as far gone as the future meat-sicles themselves.  So what can I say?  Look, when I meet people who really care about the remote future, who talk about ending all the suffering in the universe like others talk about finishing an NSF proposal, who follow their chains of logic straight past the acceptably-quirky into the “childish,” “weird,” and “naïve” without even noticing the “WHAT WILL PEOPLE THINK?” danger-signs … a little twelve-year-old nerd buried deep in my psyche can’t help but rock approvingly in his chair.

The 2009 Singularity Summit: “Advancing the messianic dream of Jeremiah, Isaiah, and the other ancient Israelite prophets … this time with more overclocked RAM and less overgrilled ram.”

Follow

A year ago, I wrote a blog entry seeking summer students to create a Worldview Manager: a web application that would prompt users to state their beliefs about various statements, and then notify them if two or more answers were in “tension” with one another, giving them the chance to modify their beliefs and thereby resolve the tension.  The idea was then covered in a short piece by Lee Gomes at Forbes.com.

I ended up selecting two students: Louis Wasserman of the University of Chicago, and Leonid Grinberg of Belmont High School.  They excelled at all aspects of this project, from low-level hacking to high-level design decisions.  If there are enough young ‘uns like them, I feel better about the future of the United States.

As a result of their work, I’m pleased to announce that you can now try Worldview Manager here.

Currently, we have only a limited selection of “topic files”, all of them rather nerdy: Complexity Theory, Strong AI, the Axiom of Choice, Quantum Computing, Libertarianism, and Quantum Mechanics.  However, if there’s enough interest, we’ll probably add more topic files soon.  In the meantime, if you have any interest in contributing topic files yourself, please let me know!  It’s actually not hard.

And if you have praise, gripes, constructive feedback, nonconstructive feedback … hey, the comments section is right underneath this sentence.

Follow

I’m writing from the Barriers in Computational Complexity workshop in Princeton, where too many real things are happening for me to blog about nothing.  I understand that streaming video of all the talks will be up eventually; for now, a few highlights:

• On Tuesday I hosted a panel discussion on “Barrier Problems in Boolean Complexity.”  The panelists were Steve Cook, Avi Wigderson, Russell Impagliazzo, and Sasha Razborov.  We got lots of questions from the floor, about everything from whether P≠NP, to whether P vs. NP is independent of set theory, to whether the laws of physics can be understood as computer programs.  Alas, there were few to no serious disagreements among the panelists (indeed, you can probably guess their answers to the last three questions).

• I gave a talk entitled Has There Been Progress on the P vs. NP Question? (The link goes to the PowerPoint slides.)

• Ketan Mulmuley spoke about Geometric Complexity Theory (GCT), his approach to P vs. NP and related problems based on algebraic geometry and group representation theory.  For months I’ve been planning a blog post about GCT. Spurred on by people at the workshop, I might actually finish it soon.  In the meantime, those of you who can’t wait for your daily helping of plethysms, Weyl modules, G-varieties might want to check out Mulmuley’s new complexity-theoretic overview and complementary mathematical overview of GCT.

• Ben Rossman spoke about recent lower bounds in circuit complexity: an ~n^k/4 lower bound on the size of AC⁰ circuits computing the k-clique function, and (a brand-new result) an ~n^k/4 lower bound on the size of monotone circuits computing the k-clique function, even on average.

• Ran Raz gave an awesome talk on “How to Fool People to Work on Circuit Lower Bounds.”  (Answer: by giving them completely innocuous-looking mathematical problems, without telling them that the answers would imply breakthroughs in complexity theory.  Alas, presumably no one who attended Ran’s talk—or for that matter who’s reading this entry—can be fooled, since we’re in on the secret.)  In particular, Ran spoke about his STOC’08 paper on elusive functions, as well as some brand-new work on how lower-bounding the rank of explicit tensors would lead to circuit and formula size lower bounds.

Meanwhile, Lance has a superb survey article in Communications of the ACM about the status of the P vs. NP problem.

(An earlier version of this post discussed a preprint by Gus Gutoski on quantum multi-prover interactive proof systems.  That preprint has since been retracted.)

And now I bid adieu, as the next talk is starting and my laptop is running out of batteries.

Follow

Here it is.  It’s mostly about the Singularity and the Many-Worlds Interpretation.

(I apologize if Eliezer and I agreed too much, and also apologize for not quite realizing that the sun was going to set while I was speaking.)

And here’s the discussion that already took place over at Eliezer’s blogging-grounds, Less Wrong.

Follow

(See also: Umeshisms, Anthropicisms)

Why, in real life, do we ever encounter hard instances of NP-complete problems?  Because if it’s too easy to find a 10,000-mile TSP tour, we ask for a 9,000-mile one.

Why are even some affluent parts of the world running out of fresh water?  Because if they weren’t, they’d keep watering their lawns until they were.

Why don’t we live in the utopia dreamed of by sixties pacifists and their many predecessors?  Because if we did, the first renegade to pick up a rock would become a Genghis Khan.

Why can’t everyone just agree to a family-friendly, 40-hour workweek?  Because then anyone who chose to work a 90-hour week would clean our clocks.

Why do native speakers of the language you’re studying talk too fast for you to understand them?  Because otherwise, they could talk faster and still understand each other.

Why is science hard?   Because so many of the easy problems have been solved already.

Why do the people you want to date seem so cruel, or aloof, or insensitive?  Maybe because, when they aren’t, you conclude you must be out of their league and lose your attraction for them.

Why does it cost so much to buy something to wear to a wedding?  Because if it didn’t, the fashion industry would invent more extravagant ‘requirements’ until it reached the limit of what people could afford.

Why do you cut yourself while shaving?  Because when you don’t, you conclude that you’re not shaving close enough.

These Malthusianisms share the properties that (1) they seem so obvious, once stated, as not to be worth stating, yet (2) whole ideologies, personal philosophies, and lifelong habits have been founded on the refusal to understand them.

Again and again, I’ve undergone the humbling experience of first lamenting how badly something sucks, then only much later having the crucial insight that its not sucking wouldn’t have been a Nash equilibrium.  Clearly, then, I haven’t yet gotten good enough at Malthusianizing my daily life—have you?

One might even go further, and speculate that human beings’ blind spot for this sort of explanation is why it took so long for Malthus himself (and his most famous disciple, Darwin) to come along.

Feel free to suggest your own Mathusianisms in the comments section.

Follow

Update (8/19): I’ve answered most of the remaining questions and closed this thread.  If your question wasn’t answered earlier, please check now—sorry for the delay!  And thanks to everyone who asked.

This blog was born, in part, out of existential anguish.  My starting axioms, reflected in the blog’s title, were that

1. nerds like me are hothouse plants, requiring a bizarre, historically-improbable social environment to thrive in life;
2. if such an environment ever existed, then it didn’t survive one or more major upheavals of the twentieth century, such as the sexual revolution, the Holocaust, or the end of the Cold War;
3. I and other nerds were therefore essentially walking fossils, absurdly maladapted for the civilization in which we found ourselves (even, ironically, as that civilization relied more than ever on nerdly skills); and
4. all that being the case, I might as well kill some time by proving quantum complexity theorems and writing a blog full of crass jokes.

And therein lies the problem: this summer, I’ve simply been enjoying life too much to want to take time out to blog about it.  Happiness, it seems, is terrible for my literary productivity.

Still, enough people now rely on this blog for their procrastination needs that I feel a moral obligation to continue serving them.  So to overcome my own procrastination barrier, from now on I’m going to try writing entries that are basically just “requests for comment”: stones in a stone soup, with the intellectual barley, discursive salt, argumentative carrots, and dialectical beef chunks to be supplied by you, my readers.

(To a few commenters: thanks so much for the plywood, rotting raccoon carcasses, and used syringes, but the soup should be fine without them…)

To start things off, today we’re going to have another open thread.  You can ask pretty much anything; my one request is that you don’t ask for grad school or job application advice, since we already covered those things ad nauseum in two previous open threads.

Here are a few examples of things to ask me about:

1. My recent trip to the Azores for the FQXi Conference on Foundational Questions in Physics and Cosmology

2. My recent trip to Paris for the Complexity’2009 conference

3. My recent trip to Lexington, Kentucky for the Quantum Theory and Symmetries conference

4. The recent breakthrough paper by Jain, Ji, Upadhyay, and Watrous, finally proving what many in the quantum complexity world long suspected: that QIP=IP=PSPACE.  That is, quantum interactive proof systems provide no more computational power than classical ones.  (For more see this post from Lance and Steve Fenner, or this one from the Pontiff.)

5. The exciting new Polymath Project, to find (under some number-theoretic assumption) a deterministic polynomial-time algorithm for generating n-bit primes.  (Hat tip to Ryan O’Donnell.)

Oh, one other thing: while you’re welcome to ask personal questions, they’ll most likely be answered not by me but by Pablo the PSPACE Pirate.

Update (7/31): One question per person, please!

Follow

Recently someone asked me how to give funnier talks.  My first response was to recoil at such an insolent question: doesn’t everyone know that at the core of my shtick lies a unique and ineffable je ne sais quoi that can’t be packaged, bottled, or resold?  But the truth was not that I couldn’t give advice; it’s that I didn’t want to.  For if everyone knew how easy it was to keep an audience at least half-awake, how would people like me maintain their edge?  By proving better theorems?  Having something new and relevant and say?  These questions answer themselves.

But because I love you, my readers, so deeply, and because I feel guilty about abandoning you for so long, I shall now publicly deconstruct the main ingredients of seminar humor, insofar as I’ve been able to find them.  (A few ingredients are specific to theoretical computer science, but most are more general.)

1. Make fun of people in the audience.  (Of course, you have to do it in such a way that they’re flattered you’re ripping them and not someone else.)
2. Ridicule bogus claims related to your topic, particularly claims that received wide currency in the popular press.  (To be honest, I do this not so much because it gets laughs—though it does—but as a small service to humanity.  If I can make one budding crackpot think twice before hitting “Submit” on a disproof of Bell’s Theorem, I will not have lived in vain.  Of course, the ridicule should always focus more on ideas than people; and even then, a few in the audience will frown on it, considering it unscientific or unprofessional.  Forty or fifty crackpots ago, I agreed with them.  It’s only experience that hardened me into a vigilante.)
3. Incorporate the audience’s shared experiences into your talk (without making a big deal of it, as if it’s the most natural thing in the world).  For example, when it comes time to trot out an Alice/Bob scenario, have yours wryly comment on a previous talk, an excursion everyone went on, a current event (like an election) that everyone actually cares about more than the talk…
4. Self-deprecate.  (“My first conjecture was falsified.  The following conjecture hasn’t yet been falsified, and is obviously true…”)
5. Say things that recognize and comment on how neurotic the thought-process of theoretical computer scientists really is, by taking that thought-process to extremes.  (“That’s off by a factor of 10^{10^120}, which is only O(1) and is therefore irrelevant.” “For years, people tried unsuccessfully to prove this sort of impossibility result was impossible.  Our result shows the impossibility of their goal.”)
6. If your field is interdisciplinary, the humor potential is almost limitless.  Are you a physicist?  Ridicule the computer scientists.  A computer scientist?  Ridicule the mathematicians.  A mathematician?  Ridicule the economists.  Chances are, enough differences in notation, terminology, assumptions, and underlying goals will arise in the talk to give you a never-ending supply of material.  “Disciplinary humor” is a more refined, intellectual variant of ethnic humor, and is effective for the same reasons.
7. Explain your results in an unusually vivid or graphic way.  (“If, at the moment of your death, your whole life flashed before you in an instant, and if while you were alive you’d performed suitable quantum computations on your own brain, then you could solve Graph Isomorphism in polynomial time.”)  This type of humor is my absolute favorite: on a plot with laughter volume on one axis and scientific content on the other, it’s way out on the upper-right-hand corner.
8. If you’re using PowerPoint, take full advantage of its comic potential: wild animations, text that pops up on the screen to question or even flat-out contradict what you’re saying, a punchline at the bottom of the slide that only gets revealed when you press a key, etc.  I love doing this because I have as much time as I need to “precompute” jokes (though I’ll then often elaborate on them extemporaneously).
9. Banter with the crowd: if someone makes a crack at your expense, always respond, and even escalate the interaction into a “staged fight” (the rest of the audience will love it).  If someone catches you in a mistake, or you don’t know the answer to a question, make a self-deprecating joke that acknowledges the situation even as it wins you sympathy points.
10. Have high energy!  Loud, lots of moving around, emotion in your voice … like you can’t wait to invite everyone along to the most exciting journey in the history of the universe.  Not only is that good practice in general (at the least, it keeps the audience from falling asleep), it also creates a general atmosphere in which it’s okay to laugh at jokes.
11. Pause a few beats before the punchline.  (You can get better at this by watching professional comics.)
12. Experiment!  If a particular joke bombs, drop it from your rotation; if it brings the house down, recycle it in future talks.  Of course, you should drop a joke once it reaches its saturation point, where much of the audience has already heard it in previous talks.  On the other hand, if this particular audience hasn’t yet heard the joke, disregard your own internal sense of its being “tired”: it could go over just as well as the first time, or better.
13. Steal ideas shamelessly from other speakers.  (I mean their humor techniques, not their results.)  Just as importantly, study the lame jokes other speakers use, so as to avoid them.  (For example, I estimate that 94% of quantum computing talks include a heavy-handed comment about someone or something being “in superposition”; this has not yet gotten a laugh.  Or the talks repeat stories about Feynman, Bohr, etc. that everyone in the audience has already heard a thousand times.)
14. Tailor your jokes to the audience’s background.  For instance, I have some jokes that work great in the US, but sink in other countries.  Or work on physicists but not computer scientists, or vice versa.
15. Make jokes about the country you’re visiting.  Of course, this is subject to common sense: I’ve been known to resort to “zed” / “aboot” jokes in Canada, scone / royalty / powdered wig jokes in England, and neutrality / yodeling jokes in Switzerland, but I usually don’t make the first joke that pops into my head when visiting Germany or Austria.
16. Take risks!  Here’s an Umeshism: if some of your jokes don’t flop, then you’re not being bold enough.  Do things that people can’t believe anyone would actually do in a talk.  Most people seem to operate under the assumption that when they’re giving a talk, they have to be less funny than in regular conversation, when the truth is the opposite.  If something comes into your head that’s funny to you, and it passes the most flimsy and cursory of offensiveness checks … out with it, and worry later about the consequences!

Three final remarks.

First, reading over the list, I can’t help but feel sheepish about how much one can do with such a crude and obvious bag of tricks.

Second, I only wish I applied this crude bag more consistently!  Particularly when I have a new result and I’m excited about the proof, I all too often ignore my own advice and lapse into boringness.  But at least I notice I’m doing it, get annoyed at myself, and resolve to be crasser, less mature, and less professional the next time around.

Third, you might feel that adding shtick to your talks makes you “shallow,” that all that should matter is the content of your results.  In the relatively rare case where you’re addressing experts in your own sub-sub-subfield, that’s probably true: you can drop the funny business and get straight to the point.  In all other cases, I’m almost certain the audience will understand your results better if you incorporate some shtick than if you don’t.  But hey—it’s up to you whether you want to address an ideal Platonic audience (“more lemmas! no irrelevant distractions! yes! harder! faster!”) or the actual flesh-and-blood hairless apes who are dozing off in the seminar room while you speak.

Follow

Avi Wigderson has asked me to announce that Princeton’s recently-founded and delightfully-named Center for Computational Intractability will be holding a week-long workshop on Barriers in Computational Complexity, this August 25th to 29th.  Apparently I’m even co-organizing one of the sessions.  So register now!  Lowerbounderati, provers of meta-impossibility theorems, and other congenital pessimists are particularly discouraged from not attending.

Follow

No doubt many of you already know … but for the rest, today’s xkcd comes impressively close (at least, I think it does) to solving the ancient philosophical riddle of how to convey what “being a nerd” feels like to someone cool since birth.

Follow

Anyone who follows the theoretical computer science blogs knows that two peoples—the Technicians and the Conceptualists—have been warring over the same tiny piece of land (the STOC/FOCS accepted papers list) for well over a generation.  The most fundamentalist of the Conceptualists believe that STOC and FOCS were promised to them in a divine covenant with Merlin, while moderates simply point out that the Conceptualists have maintained a continuous presence in these conferences since the time of Cook and Karp, always turning STOCward in prayer on the day of the submission deadline; and that, if not for STOC and FOCS, conceptual papers might get wiped entirely off the face of the earth (or worse, shunted to CCC).  For their part, the Technicians see the Conceptualists as unwelcome usurpers, infiltrating an ancient land of log factors with bizarre new models and definitions; and suggest that, if the Conceptualists feel so wronged by physicists, biologists, and economists who refuse to see the natural and social worlds in computational terms, then let the physicists, biologists, and economists give the Conceptualists sessions in their conferences.

To many of us, it’s become increasingly clear that the only long-term solution to this bitter conflict is partition: two sets of conferences for two peoples with irreconcilable intellectual aspirations.  (A few old-timers, such as Noam Chomsky, still advocate technical and conceptual papers side-by-side in the same conference, but others consider Chomsky’s proposal as quaint and outdated as his hierarchy.)

And thus I’m pleased to point my readers to two new conferences, one for each people, the first of which has the further merit of actually existing:

• Innovations in Computer Science (ICS) (“encouraging new ideas, approaches, perspectives, conceptual frameworks and techniques”), to be held for the first time January 4-7, 2010 in Beijing.

• SLOGN (“a new conference in theoretical computer science, narrowly construed, encouraging difficult arguments, analyses, and algorithms”), to be held April 1, 2010 atop Mount Everest.

Mihai Pătraşcu—arguably the most irăşcible of the Technicians—has announced his support for the new ICS conference, stating that ICS “seems like one of the best ideas in decades for improving the quality of STOC/FOCS.”  As one of the handwaviest of the Conceptualists, I wish to announce my wholehearted support of SLOGN, for precisely the same reason.

And if Mihai and I are in complete agreement about how the field should evolve, what could there possibly be to argue about?  Shalom, Salaam, and QED.

Follow