Time to Cash It In

The US tries again with a new series of one dollar coins but will again fail since we still have the dollar bill. I have heard calls for eliminating the dollar bill and the penny since I was a kid and we have had over 300% inflation since then. Americans are no more likely to give them up than their yards and gallons.

So how about something more radical? Let's give up currency all together. No more coins. No more bills. I use electronic transactions, mostly my credit card, for nearly all purchases now. Many places don't require a signature for under $25, making the transaction faster than cash. I don't even slow down to pay tolls anymore on the Illinois Tollways. Surely we can make that final push to remove cash from the rest of the transactions.

We certainly have the technology today to eliminate currency. There will be some costs involved but with the savings for the government, banks and businesses of not having to deal with cash, we should be able to supply all Americans and visitors with smart cards. We can even put pictures of presidents on the cards to keep with tradition.

Avoiding the Two-Body Problem

The two-body problem, finding two academic jobs in the same city, is becoming an epidemic in American universities. Some administrators have estimated nearly half of all new junior hires have some sort of two-body problems that needs to be solved. Many academic couples settle for jobs at places not as strong as either could have found independently.

Why have we seen an increase in the two-body problem? There is less of a gender imbalance in Ph.D. students, particularly in the sciences, than in the past. Most Ph.D.'s spend nearly all of their working and social lives with their fellow students and romantic entanglements naturally develop.

How do you avoid the two-body problem? Find yourself a non-academic partner. You may spend the rest of your working life spending time with academics, do you really want to spend your non-working life with them as well? You have to work to find a non-academic partner. Join some clubs, preferably outside the university, that match your interests. You'll meet people who share at least one interest with you. Use the on-line dating sites, let friends set you up. It will take some work to find a partner but maybe you'll fall in love with some nice MBA. That's what happened to me.

Of course you may just end up in an academic couple. After all, you just can't stop true love.

On NP in BQP

In the wake of a misleading Economist article on the D-Wave quantum computer, Scott argues why he believes quantum computers cannot efficiently solve NP-complete problems, i.e., that the complexity class BQP does not contain NP. Let's look at that question purely from a computational complexity viewpoint.

Ideally we would like a mathematical proof that NP ⊄ BQP. But any such proof would imply P≠NP, one of the great open problems in mathematics.

Moving on, complexity theorists give evidence that a statement Q is false by a "Pigs Can Fly" argument, by showing that Q implies something else we don't believe. For example

• If there are sparse NP-complete sets then P=NP.
• If NP has efficient probabilistic algorithms (NP⊆BPP), then the polynomial-time hierarchy collapses.
• If good pseudorandom generators don't exist then exponential time has small circuits.

But we don't have any known consequences of NP⊆BQP.

What we do have is the result of Bennett, Bernstein, Brassard, Vazirani that BQP can't solve black-box NP problems, a relativized separation of NP from BQP. Relativized results like this don't tell us whether or not a statement is true, just that any proof that NP in BQP would require nonrelativizing techniques. So the sentence from the Economist article

In principle, by putting a set of entangled qubits into a suitably tuned magnetic field, the optimal solution to a given NP-complete problem can be found in one shot.

does not reflect current knowledge.

Can one have a nonrelativizing proof that NP is in BQP? We do have precedent. My very first theorem gave a relativized world where co-NP does not have interactive proof systems. We published the result in a 1988 paper Are there interactive protocols for co-NP languages? and we conjectured the answer was no. We were wrong.

But so far interactive proof and related systems have been the only source of reasonable nonrelativized proof techniques that we have seen in computational complexity and we haven't had any success using this algebraic structure of arithmetized satisfiability to make efficient quantum algorithms for NP problems.

I do conjecture that NP ⊄ BQP and most computational complexity theorists would agree with me. But until we see some negative consequences of NP in BQP, computational complexity theory has so far failed to give any real evidence that NP ⊄ BQP. We believe that NP ⊄ BQP for the same reason we believe that there are no probabilistic polynomial-time algorithms for Factoring—despite considerable effort, failure to find any algorithmic techniques that might solve the problem.

Organizing the Academic Job Market

The Economists have a Job Market Wiki listing interviews and offers in mostly academic economics departments. The wiki is far from complete and likely not entirely accurate but it does allow candidates and departments to see how the competition is doing.

This year the American Economic Association started a signaling process where each candidate can signal interest in up to two departments through a centralized AEA web site. The AEA also organizes a meeting each January whose main purpose is to provide a centralized location for job candidates and departments to have short interviews with each other.

In the computer science job market, departments start off interviewing similar sets of top candidates and until those settle do schools start looking at the next tier of still rather strong applicants. The CS academic hiring season starts in January and often lasts through June or later and this year is shaping up to be no exception.

Structurally the fields of computer science and economics have much in common—culturally diverse fields from the very theoretical to the very applied. But when it comes to the academic job market, economics and most other fields have a structured process that streamlines the search while CS remains quite ad hoc. Computer science needs some central authority to bring some organization to the process but beyond posting paid listings, the ACM and CRA currently do little to facilitate the hiring process.

Henzinger on Algorithms

A reader writes about coming across a 2003 CIO article about Google Research Director Monika Henzinger and being quite surprised to read the following:

But it was while teaching courses on her beloved algorithms at Cornell University when she had a flash. "I realized that efficient algorithms were fun but not very useful to the world anymore," she says.

The reader asks if there any reasonable sense in which that could be true?

While most algorithms developed by theorists have little practical value and will never see code, efficient algorithms play a critical role in any large system, especially at Google. As Henzinger states herself later in the same article:

If you think Google is fast, it's because we have good algorithms.

Turing Award

Frances Allen will receive the 2006 Turing Award (the most prestigious CS prize), the first woman to win the award (via USACM).

Graduate Student Guide

I have received some questions recently asking me advice for topics on which I have previously posted. So here are links to postings to help your graduate school career from cradle to grave.

• Judging Applications
• Choosing a Graduate School
• Choosing an Advisor
• Finding Problems to Work On
• Attending Conferences
• Writing a Dissertation
• Looking for Academic Jobs
• The Academic Interview Trip
  • What to Wear
  • The Job Talk
  • Meeting with Faculty
• Negotiating Your Offer

Above all, have fun!

STOC and FOCS

As many of you already know, the accepted papers for STOC '07 has been posted. And in that great circle of theory life, the FOCS '07 Call for Papers is out. Submission deadline is April 20 and FOCS will be held October 21-23 in Providence.

One of my readers broke down the STOC accepts by area. Also check out the FAQ sent with the paper comments, though I doubt "No reviewer liked my paper. How come it was accepted?" gets frequently asked.

For those authors of the 234 papers not accepted to STOC: Maybe your tastes don't match those of this committee, maybe your paper is just not STOC-worthy, or maybe life just isn't fair. In any case, don't get angry, just go update your paper with the reviewer's comments and submit your paper to a journal or another conference.

Time and Music

Two quirky computer events over the vacation.

I enter events in my online calendar in Lance-time, i.e., at the time in the time-zone I will be in when the event occurs. Calendar programs don't have Lance-time so I just use Central time. Normally not a really big problem since I just leave the calendar in Central time when I travel. But on this trip I downloaded my calendar to my mobile phone. My mobile phone knows what time-zone I am in so it automatically adjusts the clock (which I like) but also the calendar. So say, an 8 PM flight out of LA, would come up as 6 PM. Software being too smart for its own good.

During my vacation a new folder "Mike's Music" popped up in Itunes. Quite an impressive collection, including the Beatles, CSN&Y and Bruce Springsteen, most of it quite playable. I don't know who you are Mike, or how your music ended up on my machine but thanks for the tunes.

Now that I returned to Chicago the music disappeared without a trace. Go figure.

MARTIN DAVID MEMORIAL (Part II- by Clyde Kruskal)

Guest Posting for Guest Blogger Bill Gasarch,
Guest Poster Clyde Kruskal.

At my fathers memorial service, here is how
I ended my remarks.

I want to share a story that is
about my kids, my Dad, and Donald Knuth.
As you will see, it all ties together.

The way Dad learned about surreal numbers, which
became his passion, is by
reading a book by Donald Knuth, written
in the form of a dialog.  Donald Knuth is in many
ways the father of computer science.  In the 1960's
he wrote a three volume set laying out the foundations
of computer science.
The world has been patiently waiting since 1973 for
Volume 4, which is just now coming out.

Anyway, you know how Dad was when he read something.
He had to make sure every technical detail was correct,
and he never missed a typo.  After finishing the book
he sent Knuth a long list of corrections,
and was surprised to get a check back in the mail.
It turns out Knuth pays money to the first person
who finds each error in his books.

If I am allowed to interupt myself, I sent this story
to Knuth.  He wrote back that he

``... found a copy of the letter I wrote to your dad in
August, 1975.  It closed with `...your reward check is
enclosed. It's the first time I've ever paid out for
{\sl Surreal Numbers\/}; in this kind of book
[written as a dialog], I can usually claim that errors
were intentional.' ''

Well, two summers ago my colleague Bill Gasarch decided
to review a math book, which happened to be written in the
form of a dialog.  So, one afternoon, he gathered
[my triplets] Alexander, Justin, and Rebecca together,
taught them the material, and wrote down their comments
as a dialog.  Of course, anything that had to do with
both math and the kids I emailed to dad, because he
would appreciate it.  Sure enough, back came a full
page of unsolicited corrections and improvements.
Bill was amazed.  After making the edits, the review
was sent out with Bill and the three kids as authors.
It appeared in the fall.

Last month I was in Bill's office and he says.
``Look.  I just got email from Donald Knuth.''
Here's what he says about the review.
``Brilliant.''
Then it goes on to ask if he has received Volume 4 yet
to review
``possibly with the help of Alexander, Justin, and Rebecca.''

I thought to myself.  ``Wow!  I can't wait to tell Dad.''

But I couldn't.
So, I hope you heard this.
We miss you.

MARTIN DAVID KRUSKAL MEMORIAL (Part I)

Bill Gasarch again.

Martin David Kruskal was a brilliant Mathematician
who passed away in late December, at the age of 81.
       (His brother Joe, still alive, did Min Spanning Tree.
More on his whole mathematical family later).
He has three children: Karen, Kerry, and Clyde.

Clyde is a theorist in my dept who works on Parallelism.

The memorial for Martin (Feb 11, 2007) was unusual.

When someone passes away there may be a memorial service
where people take turns saying things about the deceased.
The family organizes this.

When an academic passes away there may be a conference held
in his honor (invited talks from people who knew his work).
His collegues organize this.

For Martin Kruskal they had BOTH ON THE SAME DAY!
The intent was that people would GO TO BOTH.
From 1:30-3:30 there were five 20-minute technical talks
about his work.
The speakers were warned that that many lay people would attend.
From 4:00-5:30 there were seventeen 3-minute presentations
about Martin Kruskal, the person.

0) It was held at Princeton in the math building-
like a real conference.

1) The Tech talks were GREAT if you knew just a LITTLE
bit of math. People completely outside of math may have
had some problems following some of it, but they still got
the impression that Martin did great work.

2) The Tech talks had far more personal touches than most
tech talks have.
  The Memorial talks had far more math stories in them than most
memorial talks have.

3) There were between 250 and 300 people there!
Free dinner! No registration fee!

4) Karen Kruskal remarked that Clyde was the only one
of the three children who went into mathematics, and hence
Clyde understood his fathers work.  Clyde would be the first
to tell you that this is not true.  Lay people (she's a lawyer)
do not realize just have vast mathematics is.  To her, Clyde
who works on parallel computation, and Martin, who works on
the mathematics of soliton waves, both do math, and hence
understand each others work. She was half right.

5) Martin had two brothers and two sisters. All three brothers
were first rate mathematicians:
Joe Kruskal: Kruskal MST, Kruskal Tree Theorem on Well quasi orderings,
               Kruskal-Katona theorem
Bill Kruskal: Kruskal-Wallace test in statistics (deceased)
Martin Kruskal: Soliton Waves, Kruskal Coordinates, Plasma Physics. (deceased)

6) Joe Kruskal spoke about how Martin taught him math
at a very young age. (Joe was younger than Martin.)

7) Kerry Kruskal sang a song he wrote, to the tune of
GUYS AND DOLLS, about Martin's work in Mathematical Physics.
I have a copy- Until they put it on YOU-TUBE it is the
second rarest thing in my collection.

8) Clydes Triplets (Recall that Clyde works in parallelism)
performed classical music as a trio.
(Alex-Trumpet, Justin-French Horn, Rebecca-Trumpet)

9) Clyde gave an excellent talk which involved Donald Knuth,
his triples, and yours truly.  Tune in tommorow for that.

THE DEFINITION OF RARE

(Guest Blog by Bill Gasarch has has a large collection 
of novelty songs, mostly funny songs.)

I) There was a satire on Saturday Night Life called
CONSPIRACY THEORY ROCK (which was in the style of
SCHOOLHOUSE ROCK) that was brilliant, and only aired
once.  (Too controversial, though this posting is not
about that.) I have this video clip in my collection,
and it was one of the rarest things in it.

NOW this clip is on YOU-TUBE!  Hence I can no longer
claim it is `rare'.  But the YOU-TUBE clip says
``rare video footage''

HOW RARE CAN A VIDEO CLIP BE IF
ANYONE IN THE WORLD CAN ACCESS IT !?

II) With the ability to make perfect copies of CD's,
and MP3's its hard to say what it means to have a
`rare recording'.  If you have the original Vinyl
record or reel-to-reel tapes, that may be rare, but
I'd RATHER have the version put on CD or MP3.

III) Some paintings sell for gobs of money.  Do we have
the tech to reproduce those exactly (in 3D)? I suspect
no, but one day we will (holographs?).  When that day
comes, will the prices drop?  Maybe not- its already
an artificial market; `originals' may still be valuable.

IV) What music or video or TV shows or whatever bring
produced now will be considered `rare' in the future?
Note that even really bad TV shows and movies are on DVD.
Some really bad movies even have `directors cuts'.

V) So, what is the rarest thing in my collection now?
In 1976 I audio taped off of TV a satire- a Chrismas
song as if done by Bob Dylan.  I did not know who did
it.  I still don't.  I have not found it anywhere else.
It does not seem to be on vinyl, audio, CD, or MP3.
Since I have the largest Bob Dylan Satire Collection
in the world, (www.cs.umd.edu/~gasarch/dylan/dylan.html)
and this is known by that community (How large is that
community? Larger than the Gen Multidim Poly VDW
community) the fact that I can't find it, and nobody
has emailed me about it, means ... its rare! However,
I would rather FIND it on CD or some other medium and
know who did it than preserve its rarity.

READING PAPERS FOR FUN

Bill Gasarch guest blogging for Lance Fortnow

Jane: What you you been working on?

Bill: I've come up with an elementary proof of the
Gen. Multidim Poly van der Warden's theorem.

Jane: Is it new? Is it publishable? Does it have applications?

Bill: Its not new- People in the field already know this.

Jane: How many people are in the field.

Bill: Lets not go there. However, not new, not publishable as original research,
and no applications that I know of.  I got a guest post in Luca's Blog about it,
but that does not count for anything (should it?).
Anyway, here is a nice (known) corollary:

For any 2-coloring of the lattice points of the plane there exists d\in N
and a d by d^2 rectangle where all four corners are the same color.

Jane: Why did you spend time reading something with no hope for original research?

Bill: Jane, you ignorant ... (lets not go there either).

1) I was very curious about this theorem.  That is reason enough.
People don't watch Shakespeare plays for the sole purpose of getting
a paper out on them. Except English Professors.

2) Reading math or CS stuff that interests you is one way to find open
problems and new angles on things. So this is good in the long term.

3) Just because I did not plan to publish based on it does not mean that I won't.
By reading up on Ramsey Theory I have gotten out two papers, ideas for a third,
several (non publishable) ugrad and highs school projects, and a problem for the
MD Math Olympiad.

Jane: Do you always talk in lists?

Bill: Only in fictional conversations.

Is it valuable to read math of interest to you with no particular plan for application?
Clearly Yes.
But the real question is, compared to what?
Compared to reading articles more directed towards a particular problem?
Compared to working on Math Olympiad problems?
Compared to sitting and thinking?
Compared to browsing porn on the web?
The answers vary from person to person.
However, my sense is that reading for pure interest is underrated.

Complexity Papers

I am on vacation and off the internet for most of next week. Bill Gasarch will bring you his wit and wisdom in my absence.

A few of the accepted papers of the upcoming Computational Complexity Conference that caught my eye.

Extractors and Condensers from Univariate Polynomials, Venkatesan Guruswami, Christopher Umans, and Salil Vadhan.

Extracting nearly uniform random bits from weakly-random sources has been one of the solid lines of research in the past few years in complexity. This paper matches the best known bounds for extractors with a clever use of recently developed list-decodable codes.

On derandomizing probabilistic sublinear-time algorithms, Marius Zimand

I'm less excited by the title result than the tools Zimand develops, an extractor that produces bits that looks random even to circuits that can see part of the weakly random string.

Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems, Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay

When running a multiple proof system in parallel, the provers can sometimes do better coordinating between runs than treating each run separately. This paper gives an example when classically the provers can take advantage of the parallelism but quantumly they cannot.

There were several very interesting titles whose authors have not put those papers online. Shame on them.

Divestment

As an undergrad at Cornell in the early 80's, I witnessed the movement to encourage the university to divest their endowment holdings in companies that do business in South Africa, to protest the apartheid of the time. Some students went as far to create a "shanty town" of tents, sleeping outside to make their point. I didn't support their movement for a selfish reason—my mother worked for one of those companies and it seemed hypocritical to bite the hand that fed me.

Last week the University of Chicago president announced that the board of trustees would not change the investment strategies of the university in response to calls not to invest in companies doing business with the Sudanese government, despite the fact that several other universities including Brown, Harvard, Princeton, Stanford and Yale have decided to eliminate such investments. American companies are already barred from doing such business so a university could eliminate such investments reasonably painlessly but the University of Chicago didn't want to set a precedent.

Proposed NSF Budget

The president sent out his proposed budget for FY08 (starting October 1, 2007). The NSF in general and CS in particular do quite well. The CRA Blog has the details but for the tree we care about:

• The NSF received a 6.8% increase over the FY07 request.
• Research and Related Activities: 7.7%.
• Computer and Information Science and Engineering (CISE): 9.0%.
• Computing and Communication Foundation (CCF): A whopping 21.4%.

CCF is where the Theoretical Foundations cluster sits which includes Theory of Computing.

Also NSF would have a new agency wide program on Cyber-Enabled Discover and Innovation (CDI) to "Broaden the Nation's capability for innovation by developing a new generation of computationally based discovery concepts and tools to deal with complex, data-rich, and interacting systems."

The big caveat: The budget has to survive the congressional appropriation process.

The Interview Trip

A reader asks

You've told us what to wear and how to give the talk at my interview. Any tips for the rest of the trip?

Aside from your talk and a nice dinner, your interview will consist of a grueling series of half-hour meetings with faculty in and possibly outside the department. While you have passed the first test to even get an interview, you still have to distinguish yourself from the other candidates. Your job is to sell yourself particularly to people outside your field who don't know you or your research well.

Take the lead from the person you are talking to. If they start talking about their own research then listen intently and ask friendly intelligent questions. If they start talking about the town (indicating a belief that the two of you have no research interests in common) then have a nice talk comparing it to places you have lived in the past. If they ask about your own research then describe some results beyond your job talk.

Some will ask you questions. "Would you be willing to teach X, or organize Y?" Your answer is always "Yes, I'd be happy to." Some might ask why your research or even theoretical computer science in general is relevant. Make sure you have something intelligent to say and never apologize for your research. Some will ask about your ability to generate funding. Say you will regularly apply for grants at the NSF and other agencies. Acknowledge that theory grants aren't as large as more applied areas but your needs are also fewer.

You must avoid dead silence. Visit the web pages of the faculty you are meeting ahead of time and find some talking point for each of them. Have a list of questions about the department that you can always ask to keep the conversation going.

Act positively. Always show interest in what the other person says. Say only positive things about the place you are visiting and don't say anything negative about any other place. Don't complain how bad the market it. Don't complain about the hotel or the food. Don't complain about anything. Most importantly act like you really want the job whether or not you do.

Have good manners. Always firmly shake hands and thank the person you just talked to and firmly shake hands with the person you will talk with next. Act civilized at dinner. Send thank you emails soon after you return.

Good luck!

Up and Downs

I woke up to see one of my complexity submissions accepted. But soon the other two were rejected. Then the Bears lost.

The list of accepted papers for Computational Complexity has been posted. See you all in San Diego.

Bear Down, Chicago Bears

Only one topic dominates discussion in Chicago these days—the Bears in Super Bowl XLI, America's biggest sporting event. The Bears last played in the Super Bowl when I held my very first Super Bowl Party back in my first year of graduate school. The Bears won big that year and will do so again this Sunday.

I present to you Lyric Opera of Chicago's Bryan Griffin singing that famous aria Bear Down, Chicago Bears.

Or, if you prefer, the CSO Concert version.

Go Bears!

James Gray

Microsoft researcher and Turing award winner Jim Gray is missing at sea after taking his boat out on Sunday. The Coast Guard continues the search. We can only hope for the best.