Is Satisfiability Checkable?

Time for another of my favorite open questions: Is Boolean Formula Satisfiability (SAT) checkable?

The best notion of program checking comes from a paper by Manuel Blum and Sampath Kannan. Let P be a program claiming to compute a language L. A program checker M for L is a probabilistic polynomial-time Turing machine with access to P as an oracle that outputs either "P(x)=L(X)" or "P incorrectly computes x on some input."

We say L is checkable if for all oracle P and inputs x,

1. If P(x)≠L(x) then with high probability M^P(x) outputs "P incorrectly computes x on some input", and
2. If P=L then with high probability M^P(x) outputs "P(x)=L(x)".

If P is correct on x and incorrect somewhere else, M^P(x) can output either answer.

Blum and Kannan show a nice connection to interactive proofs. We say a language L has a function-restricted interactive proof (FRIP) if there is a PCP for L where the proof for x in L is computable with an oracle for L. We have the following equivalence for all languages L

1. L is checkable.
2. Both L and L have FRIPs.

Checkable languages include Graph Isomorphism, the Permanent and all of the PSPACE-complete and EXP-complete sets.

Back to whether SAT is checkable. SAT has a FRIP by using self-reduction. So whether SAT is checkable is equivalent to whether SAT has a FRIP.

All of the known PCPs for SAT seem to require counting, a prover hard for #P or at least Mod_kP for some k. Whether one can find a PCP for SAT that is even in the polynomial-time hierarchy remains open.

Perhaps one can show some consequence of the checkability of SAT perhaps that the polynomial-time hierarchy collapses. Bogdanov and Trevisan have the best result in this direction; they show that if SAT has a non-adaptive self-corrector then PH collapses to third level. Though many checking results use self-correction there still could be some completely different way to show SAT is checkable.

AT&T Research

The Newark Star-Ledger has an article about the downfall of AT&T research. Quantum Algorithms has some follow-up quotes by Bjarne Stoustrup.

No doubt that these industrial research labs can produce great ideas and results especially at the scale of AT&T or Bell Labs before the split. But the business model doesn't work; AT&T failed to capitalize on most of the innovations of its labs nor has any corporate labs with an open and unfettered research staff produced valuable intellectual property for that company. If a corporation tries to limit an open and unfettered environment, the best scientists will often leave for other labs or academia.

Bell Labs/AT&T had a lengthy history helped along by a telephone monopoly. But until someone finds the right business model, we will never see a truly self-sustaining industrial basic research lab.

Computer Science Unplugged

Can you teach basic computer science concepts to children? Without a computer?

Computer Science Unplugged by Tim Bell, Ian Witten and Mike Fellows has a wonderful collection of games and activities designed to teach young people about basic CS ideas like binary numbers, searching algorithms, text compression, information theory and much more. Some of the activities are available online. My favorite: Sorting Networks that kids can run through and find themselves ordered.

An Unnatural Post

When we see "natural" in a computer science papers it usually reflects an informal idea of realism, i.e., Clique is a natural NP-complete problem while 1-in-3 SAT is not. Sometimes though researchers use "natural" in a defined term. Generally this should be avoided--no definition can prevent artificial examples but more importantly perfectly reasonable notions that do not fit the rule are, by definition, not natural.

I work with bits and usually take my logarithms base 2, an unnatural logarithm. I use diagonalization to prove lower bounds on Turing machines, an unnatural proof technique applied to an unnatural computing model. I have even been known to use unnatural numbers, like 1/2.

What do you expect since I study an unnatural science?

Favorite Theorems: Derandomization

As I had mentioned earlier, this year I plan to write My Favorite Ten Complexity Theorems of the Past Decade II. I decided to reveal the choices one per month through the end of 2004.

For March I will go with derandomization, an area where we have seen amazing progress in recent years. My favorite derandomization result in the past decade is

P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma
by Russell Impagliazzo and Avi Wigderson, STOC 1997

The title both describes the main result and the technique use to prove it. Informally this result says that under a believable hardness assumption one can get full derandomization. Formally, if there exists a language L computable in DTIME(2^O(n)) such that there exists an ε>0 such that for all n, there are no circuits of size 2^εn that compute L on inputs on length n then pseudorandom generators exist and P=BPP.

This paper marks the culmination of a series of papers to derandomize BPP. We have also seen many papers since giving connections between derandomization and other recent areas in complexity like extractors and error-correcting codes as well as other applications for derandomization. I can't mention all of these results in this post but I recommend the survey of Valentine Kabanets and the book chapter of Peter Bro Miltersen for a broader background on derandomization.

March Madness

America's Favorite Binary Tree, the 2004 College Basketball Brackets have been released. This week last year had several posts related to the brackets intermingled with ICALP and a war.

Publishing Papers from Iran

A Chicago Tribune editorial describes an incredibly bad restriction on publishing from Iran. The U.S. Treasury Department's Office of Foreign Assets Control (OFAC) is warning publishers that they may face serious legal repercussions for editing books, papers or manuscripts from Iran or any other country that is under economic sanctions, on the grounds that such editing amounts to trading with the enemy.

Academics have always led the way in establishing relationships between politically antagonistic countries. Scientists often have the same research goals even if their politics or the politics of their countries differ. Preventing publication of their work (or in this case editing of their work) will unnecessarily restrict the communication between scientists and make opening these doors between countries harder.

More from the IEEE Spectrum.

Outsourcing and the Future of Computer Science

How will the trend in outsourcing programming work affect computer science departments in America? In the short term not good. A lesser need for programmers and continued slow growth in the technology sector will keep undergraduate enrollments down and CS departments will have less expansion. We are still a decade or two away from large retirements of the first wave of computer scientists so for the most part new faculty get hired mostly on CS department expansion.

In the long term outsourcing will lead to much stronger computer science departments. Programming skills alone will not necessarily lead to success and technology professionals will need a deeper and broader view of the tools and ideas in computer science. CS departments will have to provide courses that cover these concepts requiring a faculty that covers many areas and knows them well. Departments will have to expand to meet these growing needs with active researchers in a broad range of expertise. As a result we will see many more universities with a strong and vibrant research-oriented CS department.

Seeing the Same People in Different Places

This week I'm visiting the University of Calgary and although I have never been here before it seems like a homecoming. They have a strong quantum computing group with several people out of my past.

• Richard Cleve - I first got interested in quantum computing when Cleve had a short visit to CWI in Amsterdam during my sabbatical there in 1997. But our true bond comes from being stranded together in Tokyo after 9/11.
• John Watrous - The reason I drink my coffee black.
• Peter Høyer - Cleve and I were the foreign committee members at Høyer's Ph.D. defense in Denmark.
• Hartmut Klauck - Klauck had a postdoc at IAS while I was at NEC nearby.
• Hein Röhrig - A new postdoc in Calgary fresh from his defense in Amsterdam. Röhrig also was a summer intern at NEC.

Seeing the same faces in different places. Yet another oddity of the academic life.

SIGACT News

The first issue of 2004 of SIGACT News is out. The complexity column has part 2 of last issues' article on constraint satisfaction problems. More exciting is the list of upcoming columns: Ambainis on quantum, Guruswami on codes and Hitchcock, Lutz and Mayordomo on dimension.

Some interesting pieces in the back of the issue including information on the recent move of the editorial board of Elsevier's Journal of Algorithms to the new ACM Transactions on Algorithms and David Johnson announcing the revival of his NP-completeness column.

Right before that is a cute paper on the complexity of the peg hopping game found at Cracker Barrel (restaurant chain that serves fine American comfort food).

Remember that you can join SIGACT, support theory and get SIGACT news even if you don't belong to ACM for only $18, $9 for students.

On a different topic, the number of comments on my posts have gone up dramatically. I'm not sure why but I appreciate your feedback. I read every comment though usually restrain from responding unless specifically asked a question. I've had my say and you have your say and let's leave it at that. Often I learn something new from your comments like the Stern-Brocot tree. Keep those comments coming.

Persi Diaconis

Persi Diaconis once again shatters our belief in generating randomness; this time showing, with Susan Holmes and Richard Montgomery, that flipping coins does not usually produce uniformly random bits.

Diaconis has an impressive resume of magic, mathematics and psychic debunking. Around 1990 he visited Chicago and taught a course on Markov chain analysis spending the first half of the course on the following problem: Given n cards, pick two at random and swap them. Repeat. How many swaps do you need to get a nearly randomly shuffled deck? Answer: About n log n. The upper bound used representation theory and took several weeks to prove.

During that year, a Chicago Tribune editorial mentioned another Diaconis result showing that one needs seven standard shuffles to get a deck of cards close to random. I found the beginning of the editorial online:

And you always thought mathematicians were serious people. Especially those at Ivy League universities like Harvard and Columbia. Well ...

Dr. Persi Diaconis and Dr. Dave Bayer have just come out with a study that may give you pause. They have found, after no end of riffling and counting, that it takes exactly seven ordinary, careless shuffles to give a totally random mix to ...

Getting back to coin flipping, you can always use the von Neumann coin-flipping trick to correct for the unknown bias.

Counting the Rationals Quickly

In the November 1989 issue of American Mathematical Monthly Yoram Sagher presented a note "Counting the Rationals" giving a simple 1-1 mapping from the positive rationals onto the positive integers. Let m/n be a rational with gcd(m,n)=1. Let q₁, ..., q_k be the prime factors of n. Sagher defined his 1-1 mapping as f(m/n) = m²n²/ (q₁q₂··· q_k) With this mapping, Sagher notes you can easily determine the 10¹⁵th positive rational as 10^-8.

Unfortunately inverting Sagher's function appears to require factoring. Can one find a 1-1 mapping from the positive integers onto the positive rationals that is easy to compute in both directions? Think about it or keep reading for my solution.

Let p(i,j) = i + j(j-1)/2. The function p is an easily computable and invertible bijection from pairs (i,j) with 1≤i≤j to the positive integers. We define our 1-1 mapping from the positive integers to the positive rationals by the following algorithm.

1. Input: n
2. Find i and j such that n = p(i,j).
3. Let g = gcd(i,j) (easily computable via Euclid's algorithm)
4. Let u = i/g and v=j/g.
5. Output: g-1+u/v

Since 1≤i≤j we have 1≤u≤v making the output unique and the function easily invertible.

Marriage and the Donald

A few interesting items from this week's Newsweek.

Chicago Theory Ph.D. Amber Settle and quantum computing expert Andre Berthiaume redefine marriage.

Donald Trump lists his seven rules of success. The first four apply directly to academic research.

1. You have to be born with enough brainpower.
2. Once you have that, you have to love what you're doing. I've never seen anyone succeed who didn't love what they were doing.
3. You cannot stop. If there is a concrete wall in front of you, you have to go through it. You can never, ever give up or even think in terms of giving up.
4. Confidence is a very important thing. But confidence isn't something you develop by saying "I'm going to do this or that." You really have to believe it.

Fermat's Last Tango

While visiting Bill Gasarch in Maryland, he chose to show a tape of Fermat's Last Tango, an off-Broadway musical based loosely on Wiles and his experience with Fermat's last theorem. Instead of Wiles they used the name Daniel Keane as the person who proved the theorem. Wiles should be thankful for the name change. We stopped watching after twenty minutes. It was full of monotonous music and clichéd stereotypes of mathematicians. We turned it off after an egotistical song by the Keane character about his "love" of numbers.
According to the video jacket, we missed the love triangle between Keane, his wife and mathematics which he discusses with Fermat, Gauss, Euclid and Newton who have visited from "aftermath." I have learned a valuable lesson: Math and Science can make good drama (Breaking the Code, Proof, Copenhagen and Arcadia as examples) but it doesn't make a good musical.

Why the NSF Needs Your Grant Proposals

One of our graduate students asked me why, if the NSF has limited grant money, do our program officers actively and sometimes aggressively encourage more grant proposals? Let me explain. The NSF uses, as one of their criteria to determine the amount of funding, the ratio of proposals funded from those submitted. A lower ratio indicates higher need and may lead to more funding. Project leaders don't want to lower the numerator as this means giving out fewer grants so instead they try to raise the denominator.

Unfortunately writing a grant proposal takes a considerable amount of time and effort so many researchers are reluctant to write a proposal that has little or no chance of funding. In theory especially one can make a reasonable determination to their chances of funding so even as the number of theorists grow and the theory budget remains steady, the ratio of funded proposals remains relatively constant.

We will have to see how these rules will apply now that the theory program has been reorganized into a part of the larger Formal and Mathematical Foundations Cluster. Nevertheless if you submit a grant proposal that doesn't get funded you can take solace in the fact that you are helping the community. Doesn't that make you feel better?

My Doom

Yesterday I got an email addressed from SUNY Stonybrook with a strange attachment. I checked it with a virus checker and then stupidly opened it. Apparently a new variation of the MyDoom virus got to my computer a few hours before its virus definition was available for download. This is a reason not an excuse.

My computer is clean now but many people I know got emails with the From addressed from someone else I know. So be careful when opening your email and don't make the same mistake I did.

And for all of you Mac and Linux users out there: Go ahead and laugh. (Just anticipating the inevitable comments)

Sneakers

Time for one of my complexity-related movie recommendations. The 1992 film Sneakers describes the adventures of a professional hacking team led by Robert Redford as they go after a device that will break any code. The movie is great fun throughout and I loved the early scenes with the mathematician who created the device (which I assume has a quick factoring algorithm inside). Still I nearly screamed at the screen when he gave a seminar while standing in front of the projected slides.

Recent Turing Award winner Len Adleman served as mathematical consultant for the film. Read about his experiences here.

The LaTeX Generation

When I started college in 1981 I brought a typewriter with me. Junior year of college I experimented with a simple text processor system called script--no more white-out but my papers looked artificial.

In the first year of graduate school I used something called troff to write a term paper for operating systems. But then, just as I had my first research paper to write, LaTeX made its way onto the scene.

Back then LaTeX was relatively easy to use and did a great job with mathematics and references. Running LaTeX took a long time but boy did our papers look good. LaTeX has since become the standard in theoretical computer science papers--one has to use it because everyone else uses it. LaTeX fell far behind in user interface but still does mathematics better than anything else out there. LaTeX runs blazingly fast on today's computers but my papers look like everyone else's papers.

On a recent visit to her grandmother's house, my daughter saw my college typewriter and said "Look, Daddy's old computer." She will never know the joy of white-out.

Parberry's Guides

The most requested topic I get is for my advice for graduate students. So I would be remiss not to mention Ian Parberry's excellent guides to giving presentations and refereeing papers. There are many schools of thought on both topics but you cannot do wrong by following Parberry's advice.

Are you asking "Why do I need a guide for refereeing? Nobody sends me papers to referee." Let me know. We can fix that.

And the Accepted Papers are ....

The closest thing this weblog has to the academy awards; the list of accepted papers of the upcoming Computational Complexity Conference is up.

Is it Recursive, Computable or Decidable?

Every reader of this weblog should know about the recursive and recursively enumerable (r.e.) sets, languages accepted by Turing machines where for recursive sets the machines must halt on all inputs and for r.e. sets the machines could run forever on strings not in the language.
So where's the recursion? The terminology comes out of historically different definitions of the recursive and r.e. sets and now we're stuck with it. Or are we?
In the mid-90's, Chicagoan Robert Soare decided his field of recursion theory suffered harm with its confusing terminology. He wrote a manifesto describing the origin of the concepts and the terminology and gave a passioned argument for changing the terms to computable and computably enumerable (c.e.) sets.
Was Soare successful? Yes and no. Within his own field most researchers now use the new notation. However the fundamental concept of recursive sets goes well beyond the relatively small sub-branch of logic now known as computability theory and it will take a much longer time for these name changes to propagate throughout computer science.
Soare missed another problem of the terminology, namely the word "enumerable." This term comes from the simple theorem that the r.e. sets can be alternatively defined as those languages of strings enumerated on an infinite output tape by a Turing machine with no input.
Because of these terminological issues, Michael Sipser, in his popular textbook, uses decidable and recognizable for the recursive and r.e. sets. I understand his motivation but find the new terminology only adds to students' confusion later in their career.
Whether I use recursive, decidable or computable depends on whom I am talking to. By default I find myself using recursive not because it's the best term but because it's the one that I grew up with.

Journal of Algorithms Editorial Board Bolts to New ACM Journal

Michael Nielsen has a post linking to a post linking to a post noting that the editorial board of the Journal of Algorithms (published by Elsevier) resigned en masse to start a new journal Transactions on Algorithms to be published by ACM.

I won't rehash all of these posts but let me make two points.

1. This move is not without precedent. For example the board of the journal Machine Learning (published by Kluwer) resigned en masse a few years ago to start the online Journal of Machine Learning Research. If publishers like Kluwer and Elsevier continue with their current pricing policies we will continue to see defections. Note though that Kluwer has managed to keep Machine Learning active.
2. From Felten: Computer scientists are lucky, in that most of our best journals and conference proceedings are published by our professional societies at reasonable prices and terms. This is true for American conferences, most non-American theory conferences use Springer's LNCS series. For journals, the professional societies (ACM, IEEE Computer Society, SIAM) publish only a small fraction of computer science journals. While many of the best theory papers go to the Journal of the ACM, Transactions on Algorithms will be ACM's first journal devoted to papers in theoretical computer science.

Minimal Indices

Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds today.

Let f₁, f₂, ... be an enumeration of the partial recursive functions. We say f_i≠f_j if there is some input x such that either

1. f_i(x) halts and f_j(x) does not halt, or
2. f_j(x) halts and f_i(x) does not halt or
3. both f_i(x) and f_j(x) halt and f_i(x)≠f_j(x).

Define the set MIN as the set of indices i such that for all j<i, f_i≠f_j. How hard is the set MIN?

MIN is in Σ₂ of the arithmetic hierarchy. For all j<i you need to check that for some input x, one of the three conditions above hold (which might require a ∀ to check that a machine does not halt). We have two unbounded quantifiers (the first "for all" is bounded) so MIN is in Σ₂.

In fact this is tight for Turing reductions, every problem in Σ₂ reduces to MIN.

For an interesting open question we turn to a variation called MIN^*. We say f_i≠^*f_j if one of the three conditions above hold for infinitely many x. MIN^* contains the set of indices i such that for all j<i, f_i≠^*f_j.

Without too much effort one can show MIN^* is in Π₃. Marcus Schaefer shows that every language in Π₃ can be Turing reduces to an oracle that encodes both MIN^* and K where K is the usual halting problem. We would like to remove K which is equivalent to the following open question

Does K Turing reduce to MIN^*?

Read Schaefer's paper for details and many more interesting facts about MIN and MIN^*.

The MIT-Berkeley Axis

"I like everybody in this field" Berkeley professor Christos Papadimitriou said during his acceptance speech of the Knuth Award at the 2002 STOC conference. He paused and added "Even those not on the MIT-Berkeley axis whose papers usually do not get accepted into STOC and FOCS."

Papadimitriou was alluding to an earlier time, the 1980s, when indeed STOC and FOCS were dominated by papers (and program committee members) from MIT and Berkeley and those with strong connections with these institutions. When I attended grad school at MIT I grew to believe there was MIT theory and there was bad theory. Once I left MIT and moved off axis to Chicago I discovered whole beautiful areas of CS theory completely ignored during my MIT days.

The MIT-Berkeley axis still exists to some extent but has far less influence than two decades ago. The vagaries of the job market have forced MIT and Berkeley Ph.D.'s to spread out over a large variety of colleges and universities diluting the axis. Also the field has grown too large to be dominated by two institutions or two conferences.

Reading the Applications

I spent a considerable part of yesterday looking at applications for our Ph.D. program in theoretical computer science. Some of you readers might have an interest in what I look for in a potential graduate student. Keep in mind that other professors may read the applications differently.

Judging Ph.D. applications is not an easy task. Most of our applicants have near perfect grades (in math and TCS courses) and GRE scores (focusing on quantitative). Next I read the letters of recommendation. Nearly every recommender writes positive letters but you can definitely see some differences. "Best student in the past five years" means much more than "one of the top ten graduating CS students this year." Recommendation letters carry more weight if they show a personal contact not just "he took my class." I also pay particular attention to letters written by people I know, i.e., active members of the theoretical computer science community.

I check to see if an applicant has done any research as an undergrad (which helps but is not critical) and do a quick read of the statement of purpose. I know applicants fret considerably about the statement of purpose but in fact they carry very little weight. You can use them to explain anomalies in the application (health problems in the semester you got a C in algorithms). Trying to be clever can harm you. I remember one applicant years ago started the statement with "I want to be a graduate student because I don't want to work for a living."

Does it matter what undergraduate school you attended? We'll accept a student from any university or college, but I keep the quality of the school in mind as I evaluate the application.

Does it matter if you are a US citizen or even live in the US? Not really, though many universities including the University of Chicago have strict lower limits on TOEFL scores for incoming foreign students.

In short for me, assuming an applicant has good grades and scores, it is the letters of recommendation that make or break an application. Choose your letter writers well.

Super Theory Day at Columbia on May 14

Editor's Note: I don't plan to be an announcement server but this theory day deserves some extra publicity. Despite the self-aggrandizing it looks like quite an impressive event. Five famous speakers and most of them are known to give great talks.

The panel discussion should be quite interesting especially since Karp and Wigderson have had in the past well-publicized differing views on the topic. Read them here and here before you attend the panel.

There will be a super special Theory Day at Columbia on Friday, May 14, 2004. Theory Day, sponsored by Columbia, NYU and IBM Research, is a semi-annual conference which brings together New York Metropolitan area theorists for a day of interaction and discussion.

Why have a special one?

Because we have several reasons to celebrate:

1. Columbia University celebrates its 250th anniversary.
2. The Computer Science Department celebrates its 25th anniversary.
3. The Computer Science Theory group at Columbia celebrates its terrific theory faculty. The most recent addition is Mihalis Yannakakis.

The speakers and panelists will be:

Shafi Goldwasser (MIT/Weizmann)
Richard Karp (UC Berkeley)
Prabhakar Raghavan (Verity/Stanford)
Peter Shor (MIT)
Avi Wigderson (IAS)

Mihalis will chair a panel discussion on the future of CS theory.

To make this Theory Day really special we are planning

1. to provide lunch to the participants
2. to provide a commemorative T-shirt.

You will have to RSVP to get either; contact Rocco Servedio.

We hope you'll join us in celebrating theory in the midst of the local celebrations at Columbia.

Designing for Innovation

An interesting NSF press release describes the importance of the layout of offices to the productivity of a research group: Clustering items like refrigerator, printers, coffee makers in common areas increases chance encounters which leads to impromptu conversations and a higher level of innovation.

Such clustering may prove difficult given building layouts and worries about theft. But the study underscores that often the best research comes from unscheduled interactions between scientists as opposed to scheduled research discussions and even the simple choices of placement of offices for faculty and students should take this into consideration.

Let me throw out another question. Is it possible to get these chance encounters in cyberspace? Can we have some sort of virtual complexity coffeehouse? Or does the Internet, despite its great properties of improving communication and distributing information, actually stifle innovation by preventing those random connections we need for research?

A letter from the editors of the journal Computational Complexity

Dear friends and colleagues,

We would like to encourage you to submit suitable papers to the journal Computational Complexity (cc).

We believe that cc should be the main publication forum for papers in complexity theory. In our opinion, a high-quality specialized journal (like cc) should be a preferred option because of the following reasons:

• authors can have better impact on the field by publishing in cc, since their papers will be read by more complexity theorists.
• by having a specialized journal devoted to complexity, our community proclaims and enhances its identity.

What prompts this email is that the 2002 volume of cc was only published in 2003 and consisted of two rather than the customary four issues. This was mainly due to too few good submissions, and we did not want to compromise on quality. (The delays, in turn, caused further problems with library subscriptions.)

It is up to us, the relevant research community, to change this situation by submitting enough good papers to cc to make it flourish. Certainly, the number of high-quality complexity papers every year significantly exceeds the number we can publish, so we hope this is a realistic goal. We are committed to establishing the journal as a leading journal for papers in complexity theory.

Another advantage of publishing in cc: the publisher has a very liberal policy on copyrights and electronic versions. The copyright remains with the authors, and only the commercial-distribution rights are transferred to the publisher. Authors are free to post their work on any non-commercial forum.

You are most welcome to submit papers (via email) to us or to any member of the editorial board.

Currently, the delay between receipt of a final version of an accepted paper and its publication is quite short.

Joachim von zur Gathen (Editor-in-chief)
Sanjeev Arora (Assoc Ed)
Peter B�rgisser (Assoc Ed)
Oded Goldreich (Assoc Ed)

A Little Theorem

Here's a simple result I have seen several times recently, a bit surprising when you first see it.

Theorem: co-NEXP is in NEXP/poly.

NEXP are the languages accepted in nondeterministic time 2^poly(n). A language L is in C/poly for a complexity class C if there is a language A in C and a list of strings a₀, a₁, ... with |a_n| bounded by a polynomial in n such that x is in L if and only if (x,a_|x|) is in A.

I don't know who first showed this theorem and since the proof is rather simple it may have never been published. Let K be a complete set for NEXP and the polynomial length advice a_n for strings of length n is just the number of strings of length n in K. To nondeterministically check that y of length n is not in K, just guess a_n strings other than y of length n and verify they are in K.

This kind of result does not likely hold for NP. Yap shows that if co-NP is in NP/poly then the polynomial-time hierarchy collapses to the third level. This theorem above does not imply co-NEXP has subexponential nondeterministic circuit since exponential circuits might be required to describe the exponential computation.

Harry Buhrman noticed you can strengthen the result to show that EXP_tt^NP is in NEXP/poly where EXP_tt^NP are the set of languages nonadaptively reducible to an NP set in exponential time.

The Defense, Part II

Hein Röhrig successfully defended his Ph.D. thesis at the University of Amsterdam yesterday. The Dutch thesis defense reminds me most of a traditional American wedding. The defense takes place in a chapel. The players include the defender (Röhrig), two paranimf (the groomsmen role), the promotor (advisor, in Röhrig's case two promoters: Harry Buhrman and Paul Vitányi), a Pedel (an official position in the university now held by a woman; she plays a master of ceremonies role) and eight opponents (including myself). The defender and paranimf are in full tux and tails, the Pedel and full professors in academic gowns and the other opponents in suits. In the audience are the defender's friends and family.

The ceremony starts by the defender giving a short description of this thesis to the audience from a Podium in front of the chapel. Led by the Pedel, the promotors and opponents enter the chapel from the back and march to sit in the choir seats. For forty-five minutes the opponents, one at a time, ask hard questions to the defender about his thesis. At the end the Pedel reenters the chapel marches to the front, hits her staff on the ground and says "Hora Est" (Time has expired). The opponents and promotors march out of the chapel to a discussion room where we vote on the defense and sign the thesis. We march back in, present the diploma where the promoters read some traditional text and give a short speech.

The ceremony is followed by a receiving line and reception with dinner later on.

Call me a romantic but I truly enjoy the pomp and circumstances that accompany the Dutch defense sorely lacking in the American counterpart.

Howdy from Amsterdam

I have returned to Amsterdam for the week. I did my sabbatical in Amsterdam seven years ago and I always enjoy the visit. Yesterday I saw the soccer team Amsterdam Ajax beat NEC (the team from Nijmegen, not my previous employer). Today I am visiting CWI, the Dutch math and computer science institute in the group of Harry Buhrman (my most prolific co-author) and Paul Vitányi (who co-wrote the book on Kolmogorov complexity).

Also visiting CWI is Kolya Vereshchagin from Moscow. I had an interesting idea about Kolmogorov complexity but Vereshchagin had the same idea weeks ago. Hate when that happens.

Tomorrow is Hein Röhrig's Ph.D. defense. Hein always wanted me to mention him in this weblog having mentioned both of his officemates, John Tromp and Ronald de Wolf, before. So here is my graduation present to Hein.

STOC and the NSF

A couple of quick notes.

The list of accepted papers for the upcoming STOC conference has been posted. The most intriguing looking paper in complexity is Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size by Ran Raz (also mentioned earlier by Scott Aaronson).

Congress has finally passed the FY 2004 US budget. A 5% increase for NSF, 4.8% for research and related activities.

The Defense, Part I

You've taken your classes, passed your preliminary/qualifying exams, done your research and written your thesis. What stands between you and the Ph.D.--the thesis defense.

After all this buildup, the defense in the states is rather anti-climatic. The student gives an extended talk on his thesis research, the thesis committee peppers the student with questions, then the committee deliberates and decides whether to pass the student.

The defense is mostly for show, the student almost always passes. If the student didn't deserve to pass the fault lies not with the student but with the advisor for letting the process get this far. A dirty little secret: We often make the deliberation longer than needed just to add a little drama.

I have served on defense committees in Denmark and Portugal that follow this same basic plan. But not all countries do the same.

I remember visiting the University of Karlsruhe (Germany) when a parade broke out. I asked about the parade and my host said someone just got their Ph.D. I have also heard of some countries where the advisor has to defend the thesis. Glad I don't teach there.

I bring this up because next week I sit on my third committee at the University of Amsterdam. The Dutch do their Ph.D. defenses the way the way a defense ought to be done. What happens at the Dutch defense? I'll let you know next week.

John Lewis

[From Chris Fuchs]

Dear friends in the quantum information and foundations communities,

Many of you may not know it, but the concept of a generalized quantum measurement or positive-operator-valued measure was introduced in

E. B. Davies and J. T. Lewis, "An Operational Approach to Quantum Probability," Communications in Mathematical Physics 17, 239-260 (1970).

Last night, John Lewis passed away here in Dublin, his home of 28 years, from complications due to a recent surgery. He was a good man, honest and upright, and left us a deep legacy. He will be missed.

The Da Vinci Code

On my vacation I read Dan Brown's The Da Vinci Code, a very popular book I received recently as a gift. Warning: Minor spoilers follow.

I always enjoy a novel with an academic protagonist but the Da Vinci Code reads like a bad conspiracy theory using the roles of the professor and other experts to give the theory some weight. But I bring up this book in this weblog because it spends considerable time on various cryptographic schemes.

I don't blame the author for not using modern cryptography but the methods described would be laughable 50 or 100 years ago. Imagine using the password 1123581321 to guard the biggest secret in the history of religion. It only gets worst: backwards writing, simple anagrams, substitution ciphers, riddles. I suppose these make for fun puzzles for the reader but do not make for a safe secret.

The book describes one intriguing device supposedly invented by Leonardo Da Vinci called a cryptex, a small cylinder with a combination lock that will destroy its written contents if broken. However the book calls it a rudimentary form of public-key cryptography, which only tells me Dan Brown has no idea what that term means.

For a far better novel dealing with cryptography and the related paranoia, check out Neal Stephenson's Cryptonomicon.

I'm Back

Thanks to Scott Aaronson for covering for me last week. If you've enjoyed the last week, check out more of his writings. Maybe the weblog bug has bit him and he will start his own blog someday.

I feel the need to remark on Scott's advice post and comments, particularly the following paragraph (having just come back from a week of skiing and no research).

So then, how do you do original research? By throwing your entire life into it. Many researchers play piano, go to clubs, sail, etc., but if they're any good they probably think about research while they're doing these things. I know grad students who never suffer the indignity of working late into the night. They go surfing with friends every weekend and are constantly away on road trips. At this rate, they'll enjoy life more than I will but won't be successful researchers.

Your success in academics, like any professional endeavor, depends in part on how much effort you put into it with the relationship far more than linear. But by no means is social life and a productive research career incompatible. Most academics eventually find a life partner and many of us have children. We have many non-academic hobbies and activities even as graduate students. The trick is to find the right balance between your academic and non-academic activities, a difficult task but far from impossible. I truly admire the massive works of Paul Erdös, but I would never trade my life for the one he led.

And now a message for Warren, the college freshman with a potential interest in graduate school. Take some computer science classes and lots of math classes, particularly probability, algebra and logic. But most important of all, don't worry about research now. Enjoy your college days, get involved in lots of activities, have an active social life. You'll have plenty of time for research in graduate school.

Scaring Away The Scientists Of Tomorrow (last post of guest blogger Scott Aaronson)

Sir Lance-lot has returned, and tomorrow will reclaim his fortress from this barbarian invader. He writes: "Thanks for blogging for me, though I hope you haven't scared away potential future researchers."

Let me state clearly what I think. The greatest perk of being a scientist is never having to doubt the value of what you do. If someone who fed starving Ethiopians, or rescued baby seals from oil spills, asked me how I justify spending my time proving complexity theorems, I might have difficulty answering; eventually I'd mumble something about basic science (along with art and music) embodying the highest aspirations of civilized humankind since the age of Democritus, and therefore being worthy of pursuit even in the face of palpable suffering. But if some regular schmo -- a sportswriter, or consultant, or homeopathist -- demanded that I justify what I do, I'd laugh in his or her face.

Other benefits of a research career include the freedom more or less to choose your hours, the satisfaction of being "the person who discovered such-and-such", the opportunity to inspire students, and copious expenses-paid trips to conferences around the world. I won't dwell on the downsides of being a scientist, both out of deference to Lance, and because the downsides are obvious to anyone familiar with cultural stereotypes.

The point I want to make is that for me, both the benefits and the downsides are irrelevant, because I can't even imagine not doing science. Having once tasted it, I couldn't go cold turkey any more than a heroin addict. What if someone solved one of my open problems, or emailed me with questions about a paper I wrote? Would I ignore that person, just as though BQP/qpoly and NISZK had never been part of my life? I mean, obviously I'd be happier were I a self-assured ignoramus who majored in marketing and mingled on the beach -- but then I wouldn't be I; I'd be a different person.

In summary, then, you should pursue a research career if and only if science to you is life's k^th greatest pleasure for some k=O(1). Thank you for reading.

[Addendum: Here O(1) is intended in the physicist's sense, not the computer scientist's asymptotic sense. You only live once.]

Algorithmic Cooling on Mars II: Mars (by guest blogger Scott Aaronson)

OK, now Mars. I'm sure you've all read about the dramatic successes of the Spirit rover, which incidentally raise two computer science questions:

1. Can a lander be programmed to scout a safe, interesting landing site during its 6-minute descent phase? (Sending pictures to Earth takes too long; the round-trip time for radio signals is about 20 minutes.) As far as I know, Spirit took photos only to gauge its speed relative to the surface, not to scout landing sites.
2. Can (and should) the Internet be extended beyond Earth's atmosphere? During the periods when Spirit is not in Earth's line of sight, two existing Mars orbiters are pressed into service as relays -- so in some sense a Martian communications network already exists. Will denial-of-service attacks and Viagra offers soon plague the solar system?

I'm sure you've also all read about the Bush administration's new vision for space exploration, which includes a manned Mars mission at an unspecified future date. Despite my no-politics mandate, Lance has often discussed science funding in this blog, so I will too. The usual rule is that sending humans somewhere (the Moon, Mars, low-Earth orbit) costs 100 to 1000 times as much as sending robots to the same place. Part of the reason is that, letting ε be the probability of a catastrophic failure, the cost of a mission increases asymptotically as ε approaches 0. Unmanned Mars landers have done well with ε around 2/3. For manned missions, by contrast, any estimated ε above (say) 1/1000 is unacceptable (although ε will always be higher in practice, as we were recently reminded).

But is human spaceflight worth the costs? Lest this post become too polemical, I'll skip the usual arguments and their rebuttals (if you don't know them, read What's New by Bob Park), and end with a question for readers. If you were the President's science adviser, would you suggest gutting the Shuttle, the ISS, and all work towards a moon base or manned Mars mission, and diverting the funds toward basic science? If so, a followup: suppose the NSF budget for theoretical computer science were quintupled tomorrow. What would be the best way to spend the money?

Algorithmic Cooling on Mars I: Algorithmic Cooling (by guest blogger Scott Aaronson)

Sorry I haven't posted for a while -- QIP has left me with nary an hour to spare. Today Leonard Schulman gave a talk whose title was announced as "Physical Limits of Heat-Bath Algorithmic Cooling on Mars." No, the talk didn't actually have anything to do with Mars; Leonard just wanted to show us his Windows wallpaper (a Mars photo), and suggest that Mars, being even colder than Waterloo, might be an even better site for quantum computing experiments.

Nevertheless, the title provides an excuse to discuss two things on my mind: Leonard's talk and Mars. I'll start with Leonard's talk. Liquid NMR quantum computing has the advantage that hundreds or thousands of quantum gates can be applied before decoherence sets in, and the disadvantage that the qubits are difficult to initialize to the standard "all-0" state. Instead, the starting state is exponentially close to the maximally mixed state. This means that in the final measurement outcome, the ratio of signal to noise decreases exponentially in the number of qubits -- so exponentially many repetitions are needed to extract a signal, negating any quantum speedup.

But is this fundamental? A few years ago Schulman and Vazirani introduced algorithmic cooling, a technique that starts with a hot, high-entropy state, then uses data compression to cool down a few qubits, at the cost of making the rest of the qubits even hotter. (As long as we're limited to reversible unitary gates, the total entropy of the system must remain constant.) The cold ("Waterloo/Mars") qubits can then be used as a quantum computer's standard initial state. The trouble is that too much chaff is needed for too little wheat: with current NMR error rates, extracting a few dozen cold qubits could take 10⁸ or 10¹² starting qubits.

A natural alternative, proposed by Boykin, Mor, Roychowdhury, Vatan, and Vrijen, is to let the qubits evolve nonunitarily; that is, interact with the environment. In physics jargon, this is called "coupling the qubits to a heat bath," even though the goal is to cool the qubits. Amazingly, it turns out that by using classical tricks (for example, mapping the basis state |a,b,c> to |a+c,b+c,MAJ(a,b,c)>, where addition is mod 2 and MAJ denotes the majority function), the qubits can be made even colder than the environment to which they're coupled. This raises a question: are there any limits to such cooling? Schulman, jointly with collaborators who I can't recall right now (one of them is Tal Mor), have given an affirmative answer. Suppose each qubit initially has bias ε (that is, is in the mixed state (1/2+ε)|0><0|+(1/2-ε)|1><1|). Then the heat-bath method can't increase the probability (that is, |amplitude|²) of any basis state above 2^-nexp(ε2ⁿ), where n is the number of qubits. This bound is essentially tight: if ε>2^4-n, then the initial state can be cooled significantly. Unfortunately, the algorithm that achieves this cooling requires order 1/ε² steps, which is exponential assuming ε is exponentially small. Furthermore, this exponential blowup seems to be unavoidable (Schulman didn't give a rigorous lower bound, but said it would be easy to obtain).

To my mind, the cooling result raises a fascinating question for complexity theory. Imagine that each generation of human beings, just as it plants trees and stores wine in cellars, starts cooling quantum states -- so that future generations, millions of years hence, could use those states to perform whatever quantum computations they wanted. "Vintage" quantum states would then be highly prized possessions (served chilled, of course). In this situation, would we be using exponential time (the time needed to cool the states), or polynomial time (the time between specifying the input and measuring the output)?

Part II of "Algorithmic Cooling on Mars" will be about Mars.

Live From QIP (by guest blogger Scott Aaronson)

As my plane descended toward Toronto on Monday, it felt as though I was landing on the surface of another planet (though maybe the Mars rover was too fresh in my mind). All I could see out the window was white snow crisscrossed by black highways. On the ground, the weather was probably the coldest I've ever experienced. Call me a wuss if you're from Alaska, northern Canada, Siberia, or Antarctica, but I did go to Cornell.

Before QIP started I visited the University of Western Ontario for a day, to work with Dan Christensen on the complexity of simulating spin-foam models of quantum gravity. We didn't get far. The trouble is that no one knows how to define measurement in these models, and the answer could strongly affect computational complexity. Maybe spin-foam models can solve graph isomorphism in polynomial time; then again, maybe they can't even simulate garden-variety quantum computers.

I took the train to Waterloo on Tuesday night, then on Wednesday hung around the Perimeter Institute, which is a converted tavern full of theoretical physicists and quantum computing people. The conference talks started on Thursday; here are summaries of a few.

• Richard Cleve spoke about some extremely cool joint work with Peter Høyer, Ben Toner, and John Watrous. They point out that the classical proof of MIP = NEXP breaks down if the two provers share entanglement -- regardless of whether the verifier is able to manipulate, or even knows anything about, quantum information. (It might still be true that multiple provers who share entanglement can convince us of any language in NEXP, but if so it will need a new proof.) Cleve et al. give explicit examples of 2-prover interactive proof systems that are classically sound but become unsound if the provers share entanglement. To me, the most exciting aspect of this work is that it offers a new, complexity-theoretic way to understand the famous Bell inequalities. In turns out that Bell inequality violation is "really" about two provers convincing a verifier that (say) a certain graph has a 3-coloring when in fact it doesn't, by using entanglement to correlate their answers to the verifier's queries.
• John Watrous spoke about stronger error reduction for QMA. Recall that QMA, or Quantum MA, is the class of languages for which there exist polynomial-size quantum proofs that convince a polynomial-time quantum verifier that an input is in the language when indeed it is. Here the completeness and soundness errors are 1/3. Early on Kitaev observed that the prover can amplify the correctness probability to 1-2^-p(n) by giving the verifier O(p(n)) copies of the proof. The verifier then checks each proof independently (destroying it in the process) and outputs the majority result. Against everyone's intuitions (or at least mine!), Watrous now shows that O(p(n)) copies are overkill -- the verifier can amplify the correctness probability arbitrarily using a single copy of the proof! This means that a "quantum library" could store proofs on the shelves, to be borrowed and returned intact by quantum patrons who want to convince themselves of the truth of various statements. The conventional wisdom -- that learning something from a quantum state always disturbs that state -- is wrong in the case of proofs. (Could this be related to zero-knowledge proofs?) Another implication of Watrous' result is that QMA_log = BQP.
• Scott Aaronson spoke about Multilinear Formulas and Skepticism of Quantum Computing. Journalistic objectivity precludes me from commenting on the excellence or otherwise of that particular talk. Next Ran Raz explained why Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size -- a brilliant result whose relevance to quantum computing is that it provides the technical tools for my talk. I'd say more about Raz's result, but it's 1AM and I have to get up early tomorrow for another day of manipulating entanglement at ultra-cold temperatures.

Advice, Not The Quantum Kind (by guest blogger Scott Aaronson)

A comment to my last post asked for advice for people interested in getting into complexity research. So here it is. Keep in mind that I'm still a grad student -- for advice from more experienced researchers, read Lance's earlier post, and this essay by physicist Steven Weinberg.

I think the key is to start doing creative original research right away. My first year at Berkeley, I took three courses a semester, hoping to prepare by stuffing my brain with knowledge. This was a mistake. Take as few courses as you can get away with, besides directly relevant ones like complexity theory. Learn what you need to know while doing research, not beforehand.

This approach has two advantages. First, you never know what you need to know until you need to know it. Not even Einstein could have predicted as a student that he'd need differential geometry to invent general relativity. And second, you don't really understand anything unless you have a personal stake in it -- meaning that you discovered it, rediscovered it, extended it, applied it, tested it, implemented it, reinterpreted it, explained it to others, etc. This the reason most students forget everything in a course right after the exam. (As Feynman said, "what I cannot create, I do not understand.")

So then, how do you do original research? By throwing your entire life into it. Many researchers play piano, go to clubs, sail, etc., but if they're any good they probably think about research while they're doing these things. I know grad students who never suffer the indignity of working late into the night. They go surfing with friends every weekend and are constantly away on road trips. At this rate, they'll enjoy life more than I will but won't be successful researchers.

I can't offer any advice on research topics, other than to solve the open problems listed in my papers. Blanket advice is difficult because your research ought to be intimately connected to who you are as an individual. Lance suggests leafing through conference proceedings until you find what excites you, while Weinberg suggests getting involved in the "messes" that nobody understands. As for me, I like to start with physical or philosophical questions (can we assign any meaning to "the past" besides memories and records in the present? is there a theory that agrees with quantum mechanics on all experiments to date but that wouldn't allow quantum computation? why should we expect information content to be proportional to area rather than volume?), and then look for related questions that can be addressed using complexity theory. But I don't know if anyone else works that way.

Ingredients for Serious Thought (by guest blogger Scott Aaronson)

To prove theorems I need a particular kind of intense concentration, sustained for hours, that I don't need for programming, fiction writing, guest blogging, or anything else I've ever done. This kind of concentration seems to come naturally to some researchers, but it never has to me. So over the past four years, I've been keeping a list of what in my physical environment and state of mind facilitates the proving of STOC/FOCS-type results. Although this list is personal and idiosyncratic (and even a bit embarrassing), I offer it in the hope that its very specificity will inspire you to add your own ingredients. Feel free to do so in the comments section.

1. Lots of light.
2. Adequate sleep the night before (duh).
3. Freedom from buzzing insects, screaming babies, ringing phones, slamming doors, and car alarms. I'll never know what I could have proved if not for these things.
4. A well-ventilated room with fresh, non-oxygen-depleted air at about room temperature. (Bug screens allow the last two ingredients simultaneously.)
5. Caffeine or other stimulants.
6. A comfortable swivel chair, or else a couch or bed to sprawl across.
7. Long deserted halls or outdoor walkways. (Pacing around in tight circles is no good.)
8. Hours and hours of concentration with no end in sight. I've never been able to set aside (say) two hours for serious work, in between other commitments. That's why I work at night.
9. Lack of awareness of how much time has elapsed with no new ideas. Before starting to work I take off my watch and hide the Windows taskbar so I can't see the little clock in the corner.
10. Comfortable clothes. I've never proved a publishable result wearing a shirt with a too-tight collar.
11. Black erasable pens, unruled paper (the backs of printouts serve nicely), Scientific Workplace for TeX, and (don't laugh) MS-DOS QBasic for quick calculations. Substitute your own favorite tools.
12. No tempting distractions. Train rides are good: plenty of room to spread out papers and a laptop, but no Internet access (something I hope doesn't change soon).
13. No people around toward whom I have strong unresolved feelings (attraction being only one example).
14. Freedom from bodily annoyances and pains. Advil, cold medicine, lip balm, a nail clipper, and a glasses cleaning cloth are important weapons in my theory arsenal. Also, I can't do serious work until about half an hour after a meal.
15. A positive attitude, which is fostered by a calm, uneventful week in my life.
16. Colleagues to talk to. People able to shoot down wrong proofs are ideal, but even "write-only black boxes" are invaluable as sounding boards. Of course I try to reciprocate both services.
17. A problem that I consider "mine" -- either because I posed the problem, I've had recent successes on subproblems or related problems, the problem is important for one of my research goals (or even better, two goals), or I'm (rightly or wrongly) seen as the world expert on the problem.
18. A problem that others are eager to see solved. It's easier to let myself down than to let others down.
19. Conference deadlines. They motivate me to work, but then if I miss them (as I do), my "research GPA" doesn't suffer: there's always the next conference.

Arrr, Even Pirates Be Polynomially-Bounded (by guest blogger Scott Aaronson)

Leaving home after the holidays, I said goodbye tonight to my friend since junior high school, Alex Halderman. You might have read about Alex in the news: Princeton computer science graduate student, breaker of music CD copy-protection schemes, and the first person ever to attain national fame for holding down a Shift key. (Alas, I tease him, my own research too often entails pressing multiple keys.)

Alex's recent run-in with the recording industry got me thinking about whether anti-piracy technology can have any theoretical basis. Passive experiences like listening to music are hard to copy-protect for an obvious reason: if you can see or hear something, then you can also record it, especially since disk space is almost never a limitation today. (Admittedly, there's some loss of quality any time you convert from digital to analog and back. Also, this theory would predict rampant piracy of books, which hasn't happened -- yet.)

The copy-protection problem is more interesting for interactive experiences like video games and application software. The standard solution -- you send the software company your computer's hardware ID, X, and the company sends you back a key f(X) that unlocks the program -- is insecure. You could always copy the unlocked program, then run it on another computer using an emulator. Whenever the program asks for the hardware ID, the emulator says it's X.

A better solution involves a program that constantly needs to communicate with a central server in order to run. For example, the program could demand a new key each time it's executed (based on its current input), which the server only supplies after getting back the previous key sent by the server. That way, any pirated copies of the program not only have to spoof IP addresses; they have to remain in communication with each other (or else be coordinated by a "renegade" server) in order to synchronize their keys.

An even more centralized solution is to run the whole program off a server and charge for each use. In this situation, a program can be "pirated" only if (in learning theory terms) the function that it computes is PAC-learnable from membership queries. The downside, of course, is the high cost in server computing time and communication latency.

Open Research Issue #1. Is there a way for the user's machine to do almost all the actual computation, yet to still need a short message from the server to "unlock" its results? If so, how much can the required communication with the server be reduced (especially the number of rounds)? Boaz Barak has pointed me to some relevant crypto papers, including this one by Sander, Young, and Yung; but the general problem seems wide open.

Of course there's always copy-protection based on physically opaque hardware, such as dongles, smartcards, or the 'Fritz' chip. Since I have no idea how secure these technologies really are, I prefer to end this post with a question more up my alley:

Open Research Issue #2. Can the No-Cloning Theorem of quantum mechanics be exploited to create unpirateable software? What we want is a quantum state ψ such that (1) a program P can be written that needs to measure ψ in order to work correctly; (2) ψ can be prepared by a polynomial-size quantum circuit, given secret information known only to the software company; and (3) a circuit for ψ can't be efficiently inferred, even given P's source code and unlimited copies of ψ. More impressive still would be if P used the same state ψ over and over, without the software company needing to provide a fresh copy for each execution. I suspect the latter is impossible. Proof?

Complexity Class of the Week: PP (by guest blogger Scott Aaronson)

Yeah, I know: PP has already been this weblog's complexity class of the week. But once you've seen how to define PP using super-powerful variants of quantum mechanics, you might never look at Probabilistic Polynomial-Time the same way again! (Then again, you might.)

Let's define PostBQP (or BQP with postselection) as the class of languages L for which there exists a uniform family of polynomial-size quantum circuits such that

• For all inputs x, the circuit's first qubit has a nonzero probability of being measured '1' at the end of the computation.
• If x is in L, the second qubit will be measured '1' with probability at least 2/3, conditioned on the first qubit being measured '1'.
• If x is not in L, the second qubit will be measured '1' with probability at most 1/3, conditioned on the first qubit being measured '1'.

In physics, "postselection" means you throw away all runs of an experiment for which a measurement of some quantity X doesn't yield a desired outcome. (Hopefully, X isn't itself what you're trying to measure - otherwise it's not postselection, it's fraud!) But you can also think of PostBQP as the quantum analogue of the classical complexity class BPP_path (another previous CCW).

Clearly PostBQP sits between BQP and PP. I became interested in PostBQP when I realized that the containment BQP/qpoly in EXP/poly (discussed earlier in this weblog) can be improved to BQP/qpoly in PostBQP/poly.

Exercise 1. Imagine that the gates of a quantum computer only needed to be invertible - not unitary. Since states might no longer be normalized, let's define the probability of measuring a basis state x with amplitude α_x to be |α_x|² divided by the sum over all basis states y of |α_y|². Show that we could decide exactly the languages in PostBQP.

Exercise 2. Now imagine that the gates are unitary, but the probability of measuring a basis state x equals |α_x|^p divided by the sum over all basis states y of |α_y|^p, where p is a nonnegative real number not equal to 2. Show that we could decide all languages in PostBQP.

I was getting more and more excited about the fundamental new complexity class I'd discovered. Alas:

Exercise 3. Show that PostBQP equals PP.

The moral is that when you make a quantum class too powerful, it turns into a classical class! (Another example of this is NQP = coC=P.)

How Long Until We Get Along? (by guest blogger Scott Aaronson)

I'm honored and humbled that Lance Fortnow decided to entrust his weblog to me for the week. Lance's only request was that I obey a few simple ground rules: keep it clean, stay on topic, don't betray confidences, and absolutely no politics.

To demonstrate my commitment to Lance's ground rules, I'd like in this first post to address the Israeli-Palestinian conflict. No, not the conflict itself, but rather a meta-question that it raises: how can so many smart, educated, well-meaning people disagree so vehemently about the most basic facts of an issue? How can they end every conversation not closer together but farther apart, "agreeing to disagree"? We can ask the same question about free markets versus socialism, the interpretation of quantum mechanics, or other issues on which two or more sides are certain of their own arguments.

A 1976 theorem of Robert Aumann has been interpreted as showing that two honest, rational people (who believe each other to be honest and rational) should never disagree about anything. More precisely, let Alice and Bob be Bayesians who assign the same prior probabilities to all random variables (admittedly a big assumption), but who have since gained different knowledge about the variables. Let p be Alice's posterior probability that (say) it will rain tomorrow, conditioned on everything she knows, and let q be Bob's posterior probability. The theorem says that if p and q are common knowledge to Alice and Bob, then p=q.

The key point here is that "everything Alice and Bob know" includes their knowledge of p and q. So for Alice and Bob to reach consensus, it isn't enough for them just to announce p and q -- for then p and q might change, so they'd need to announce the new values, and so on iteratively. However, so long as the whole probability space is finite, this iterative process will end eventually with Alice and Bob agreeing on the probability that it will rain tomorrow.

Great, you say, but what does this have to do with complexity? Well, if Alice and Bob exchanged everything they knew, then obviously they'd agree on the chance of rain. So the crucial question for me -- and one that seems never to have been addressed in the large economics and philosophy literature on this subject -- is, how many iterations are needed until convergence? Or, if we let Alice and Bob use an arbitrary protocol, then how many bits must they exchange before reaching consensus or near-consensus? In communication complexity language, instead of evaluating a function f(x,y) where x and y are n-bit strings, now we merely want Alice's expectation of f(x,y) (conditioned on her partial information about y) to equal (or nearly equal) Bob's expectation, given a known prior distribution over x,y pairs.

For some f,x,y and distribution over x,y pairs, can we show that (say) n(1-o(1)) bits of communication are needed? Such a lower bound could provide the first compelling explanation for why honest, rational friends can disagree: because they're not Siamese twins, and they don't have their entire lives to talk to each other.

Guest Blogger

I off on vacation next week and you will have a guest weblogger, Scott Aaronson, while I am gone. I have confidence Scott will keep you all entertained and enlightened. He will also bring you the latest news from the world of quantum computing from the QIP Workshop next week. Enjoy.

Balance is a Red-Hot Word

Some interesting science policy quotes courtesy of the American Institute of Physics.

Where have the Americans gone? - DOE Office of Science Director Ray Orbach discussing declining number of American university students studying physical sciences.

The decline in funding for the physical sciences has put our Nation's capabilities for scientific innovation at risk. - Senate Appropriations Subcommittee Chairman Christopher "Kit" Bond (R-MO) at NSF budget hearing

The concern expressed for the physical sciences in the budget reminds me a little bit of the old joke about the will that said, 'To Joe, who I said I would mention in my will, "Hello Joe.'" Sympathy won't fund labs. - House Science Committee Chairman Sherwood Boehlert (R-NY) when discussing FY 2004 budget request

I would like to caution you about the use of the word "balance." - OSTP Assistant Director for Physical Sciences and Engineering Patrick Looney at a DOE advisory committee meeting, regarding federal research funding allocations. Looney later called it a "red-hot word" that was "divisive."

More quotes and a roundup of 2003 science policy and budget developments. In the end it looks like a 5% increase for NSF for FY2004 (which started in November). Not bad given the rest of the budget but far less than needed to properly fund American scientific research.

Survey on Private Information Retrieval

I posted the latest BEATCS Complexity Column, A Survey on Private Information Retrieval by Bill Gasarch.

With this article I am retiring as editor of the Complexity Column. Jacobo Torán will take on the editing duties starting with the June issue.

Update 1/19: Bill Gasarch now has set up a web page on PIR.

Pictures from Mars

I grew up as an information hound. Lacking the internet in my high school days I would often hang out in the library looking things up. One day I found a catalog from the US Government Printing Office with all sorts of stuff at reasonable prices. I ordered a brochure with pictures of Mars from the 1970s Viking Missions to Mars. A few weeks later came some pretty color images including a stereographic (3D) image of the red planet.

Fast forward over two decades later. Another Mars mission. More pictures. The pictures haven't changed much but I can access them far easier and quicker than before. When you look at those Mars pictures realize that the great technological advance is not so much in NASA getting pictures from Mars but in NASA getting those pictures to you.

What is an Algorithm?

The October 2003 BEATCS has two articles discussing the Church-Turing thesis, Beyond Turing Machines by Eugene Eberbach and Peter Wegner (I can't find this paper online though I've discussed Wegner's work before) and the Logics in Computer Science column Algorithms: A Quest for Absolute Definitions by Andreas Blass and Yuri Gurevich.

Maybe it's a man bites dog thing: One cannot write an article that says, yes, Turing machines capture computation and fully describe algorithms. But I can use this weblog to say that.

Blass and Gurevich ask "What is an algorithm?" From their introduction: It is often assumed that the Church-Turing thesis settled the problem of what an algorithm is. That isn't so. The thesis clarifies the notion of computable function. And there is more, much more to an algorithm than the function it computes. The thesis was a great step toward understanding algorithms, but it did not solve the problem what an algorithm is.

Why not? The paper goes on to discuss the meaning of the Church-Turing thesis and some scenarios where they claim the Turing machine fails to capture algorithms.

• Interactive Algorithms: A broad class containing randomized algorithms, nondeterministic algorithms and asynchronous algorithms. All of these can be simulated on Turing machines and in any case the actual interaction process is always modeled by an algorithm easily implementable on a Turing machine.
• Computing with Abstract Structures: Turing machines have no problems dealing with abstract structures given a logic that describes them. Hidden parallelism is easily simulatable.
• Non-discrete computations: Yes, a finite Turing machine cannot model arbitrary real numbers. But a Turing machine can simulate any process involving real numbers to a greater precision that any physical instrument can hope to measure.

The article also discusses issue of time where the simulation issues get stickier. But in general every algorithmic process can best be described and simulated by Turing machines. There really is nothing more to it.

Freeman on CISE Reorganization

Peter Freeman, Assistant Director of NSF for CISE, has an "important message" on the recent reorganization. Good to see he's finally acknowledging the confusion about the changes, though I would still like to see more of the philosophy behind it.

I talked recently to a former program director who worries that the new clusters will make it more difficult for theory since they now have to directly compete with more applied areas. He also worries that removing power from the program director position will make it even harder to recruit good program directors in the future.

These are a few of my favorite theorems

In December of 1994 I presented My Favorite Ten Complexity Theorems of the Past Decade, a paper where I chose ten theorems representing different areas in complexity and used them as a springboard to describe the progress in my field over the previous ten years, roughly from when I started graduate school.

Hard to believe another decade has nearly passed. By the end of this year, you will see My Favorite Ten Complexity Theorems of the Past Decade II. I have no shortage of theorems to draw from though I foresee tough decisions like which derandomization result to choose.

I will keep you updated on this project as the year goes on.

End of Year Thoughts

We had another solid year for theoretical computer science and computational complexity with many exciting results such as the polynomial algorithm for perfect graphs developed in a series of papers by Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovic. We also saw a number of strong papers in derandomization, extractor construction, dimension reduction and many other areas of complexity.

In 2003 we celebrated the 100th anniversary of the births of Alonzo Church, Andrey Kolmogorov, John von Neumann and Frank Ramsey, mathematicians who work played a big role in complexity. Next up, Kurt Gödel in 2006.

Trends to watch for in 2004:

• How will the reorganization of CISE and the end of the ITR affect NSF funding for theoretical computer science?
• Will a hopefully improving economy push universities to increase their resources in computer science?
• What trends will we see in recruiting this year? More and more Ph.D.'s seem to prefer postdoc positions though the number of these positions continue to decrease, especially in industry.
• How will the choice of the US president in 2004 affect the future of scientific research in America? A critical question, but not one that a journalist will ask in any debate.

Happy new year to all! May we prove P≠NP in 2004.

John von Neumann

Today is the 100th anniversary of the birth of John von Neumann, one of the greatest mathematicians of the 20th century. Let me discuss two aspects of his work, one big, one small, that have greatly affected computational complexity.

The von Neumann min-max theorem showed that every finite zero-sum two-person game has optimal mixed strategies. More formally, let A be the payoff matrix of a game, then

max_x min_y x^TAy = min_y max_x x^TAy where x and y are probability vectors.

Andrew Yao used the min-max theorem to prove what we now call the Yao Principle: The worst case expected runtime of a randomized algorithm for any input equals best case running time of a deterministic algorithm for a worst-case distribution of inputs. The Yao principle has proven invaluable for proving upper and lower bounds for deterministic and probabilistic algorithms.

How can you get a fair coin by flipping a coin of unknown bias? You use the von Neumann coin-flipping trick: Flip the biased coin twice. If you get heads then tails output HEADS. If you get tails then heads output TAILS. Otherwise repeat. This procedure will output HEADS or TAILS with equal probability and if the bias is not too close to zero or one the expected number of repetitions is relatively small.

The von Neumann coin flipping trick is the first in a long line of research in complexity extracting random bits from weak random sources.

John von Neumann passed away February 8, 1957 in Washington, DC.

That's My State

Nothing like this Chicago Tribune story to ruin your holidays. Apparently the Illinois Board of Higher Education has launched a study of faculty productivity looking at what kind of research projects faculty undertake to how much time they spend in the classroom. According to board chairman James Kaplan "there's got to be a tangible, measurable benefit for the people of the state of Illinois for a professor doing research." Nothing good can come from this.

The University of Chicago is a private school unaffected by this study, but I would hate to see my friends at the various U. Illinois campuses to have to take unpaid leave to go to conferences.

Update 12/29: Daniel Drezner dissects this article. Also, I talked with a University of Illinois-Chicago professor who worries less about this study than budget cuts in the University of Illinois system due to the continual fiscal crisis in the state.

Scientific Superstars

On Saturday I visited the Einstein Exhibit at Chicago's Field Museum. Some manuscripts and letters and a nice exhibit explaining why time must vary if the speed of light remains a constant made this an interesting but not a must-see exhibit. The biggest surprise for me came from seeing how Einstein's fame happened overnight instead of the more gradual fame I would have expected. In 1919 a solar eclipse showed that light from stars do bend from gravitational forces. Einstein's fame grew immediately and his name became synonymous with genius.

This superstardom for a scientist doesn't seem to happen today. When Andrew Wiles proved Fermat's last theorem he did get some deserved attention but he never became a true household name. When you realize Wiles has hit the upper limit of fame a mathematician can receive (ruling out people like Ted Kaczynski and John Nash) one can see the Einstein effect of science may never return.

On the other hand, University of Chicago paleontologist Paul Sereno headlines the social page of the Chicago Tribune at the "Party With Giants." Perhaps scientists can still achieve more than fifteen minutes of fame after all.

Does NP=UP?

Time for another of my favorite open problems.

Does NP=UP imply the polynomial-time hierarchy collapses?

UP is the class of languages accepted by nondeterministic polynomial-time Turing machines that have at most one accepting computation for all inputs.

This problem has loose connections to Valiant-Vazirani but Hemaspaandra, Naik, Ogiwara and Selman have the most closely related result. Consider the following proposition.

(*) There is a set A in NP such that for all satisfiable formula φ there is a unique satisfying assignment a of φ such that (φ,a) is in A.

Hemaspaandra et. al. show that (*) implies the polynomial-time hierarchy collapses to the second level.

For all we know, (*) and NP=UP are incomparable. If (*) holds for some A in P then NP=UP by just guessing a. We don't know whether NP=UP implies (*) since the accepting computations of a UP machine accepting SAT need not reveal a satisfying assignment of a formula.

There exist an oracle relative to which UP=NP≠co-NP. A relativized world with UP=NP and Σ₂^p≠Π₂^p remains open.

Does PowerPoint Make You Dumb?

Yesterday the New York Times Magazine had its annual "The Year in Ideas" issue. Ideas Futures Markets in Everything and Proving You're Human I had discussed in earlier posts here and here. Instead let us discuss whether PowerPoint Makes You Dumb?

As an avid PowerPoint enthusiast, I found the Times discussion quite misleading. The NASA scientists followed the advice of Tufte, filling the slides full of information that made them impossible to follow. One should not try to give complex ideas in a presentation; rather give an overview of these ideas and leave the messy details to technical articles. PowerPoint makes it easy to give overview talks and hard to give talks full of ugly details, crammed slides and detailed formulas, almost always leading to better talks.

Ordering Authors

Every scientific field has their own rules for the order of authors in a paper. In theoretical computer science, tradition dictates that we list the authors alphabetically by last name. I don't agree with this tradition; rarely do all the co-authors of a paper play an equal role. The decision whether to add someone as a co-author, and thus an equal, often becomes difficult.

But breaking with tradition can have its own problems. I have three papers that break the alphabetical rule though two were in biology which has its own rules. In the other back in 1990, Carsten Lund, a graduate student at the time, made the key step in developing an interactive proof system for the permanent. For that we made him first author in the Lund-Fortnow-Karloff-Nisan paper. In retrospect I regret this decision. It only added confusion to those who cited the paper. Also did Lund not play as important a role in other papers where we kept alphabetical order? Breaking with tradition, even with the best of intentions, can often cause more harm than good.

Seven Naughty Words

Want an easy rule to greatly improve your writing? Just avoid the following words, particularly in the abstract and introduction of your papers.

am is are was were be been

Avoiding these seven forms of "to be" will force you to write in the active tense instead of the passive making your sentences less boring. For example, instead of "It is known that all functions can be computed securely in the information theoretic setting" use "We can compute all functions securely in the information theoretic setting."

Taking this rule to the extreme can lead to some very convoluted sentences but, I promise, forcing yourself to think actively about every statement you write will make a great difference in your prose. In almost all cases the right answer is "not to be."

Two Uses of Randomness

Over the last 15 years, two very active research areas seem at odds. Derandomization results have shown us that we can often remove randomness from computation but interactive proof systems and PCPs exhibit incredible power from randomness. There is no contradiction here, just two very different ways we use randomness in complexity: for searching and for hiding.

Typically we think of randomness for searching, for example finding disagreements with Fermat's little theorem to show a number is composite or taking random walks on graphs to show they are connected. Derandomization results have given us reasons to believe we can replace the randomness in these computations with pseudorandom number generators.

Randomness can also play the role of hiding, since no one can predict future coin tosses. In interactive proofs we make the jump from NP to PSPACE because of randomness. For PCPs with O(log n) queries the jump goes from P to NP and with poly queries from NP to NEXP, in the later case classes which are provable different. In all these cases the prover cannot cheat because it cannot predict coin tosses not yet made by the verifier. A verifier using a pseudorandom generator will fail here, since the prover could then predict the verifier's actions.

AM protocols have the verifier flip coins first so no hiding going on, rather searching for a statement Merlin can prove and we expect some derandomization for AM. The result that MA is in AM says that sometimes we can replace hiding randomness with searching randomness.

A Regular Problem Solved

Paz Carmi, Yinnon Haviv and Enav Weinreb from Ben-Gurion University have solved the regular language problem I posted last month.

The problem came from Janos Simon based on a homework question in Kozen's book. Let L(A)={x|x^m is in A for some m}. The homework question asked to show that L(A) is regular if A is regular. The question Janos asks was how many states do we need for a DFA for L(A) if A has n states. Carmi, Haviv and Weinreb show that an exponential number of states are required.

Not only did they solve the problem but also sent me this nice write-up of the proof. I believe this is the first time someone has directly solved a problem I've given on this weblog. I owe each of them a beer (or non-alcoholic beverage of their choice).

Update 12/9: I received the following today from Markus Holzer.

It seems that I have missed your posting about the problem last month. The problem you have stated was already solved in June by Jeff Shallit and co-authors. They have given a lower bound on the DFA accepting root, by considering the (largest) syntactic monoid induced by two generators. The latter problem on syntactic monoid size is of its own interest and I was working on that for a while, therefore I know the result of Shallit et al on the root descriptional complexity. Maybe you also owe the beers to Shallit et al.

The Elsevier Dilemma

The Cornell University Library has announced it will drop a substantial number of their Elsevier subscriptions, part of a general problem Cornell and other libraries are facing with higher costs and different pricing models from commercial academic publishers.

I have wanted to write a post on this topic for a while but I find it difficult to truly understand the problems or the potential solutions. Elsevier does a nice job with their portal and their publishing, but because of consolidation and cheap distribution via the internet, they have changed their pricing model in ways that make it difficult for many libraries to afford all of the journals that they need.

This poses some moral questions: Should we avoid submitting our papers to Elsevier journals? Is it wrong for me to serve on the editorial board of the Elsevier-published Information and Computation? I just don't know.

The NSF and SIGACT News

First an update on NSF program solicitations: The Formal and Mathematical Foundations cluster has posted its solicitation which includes computational complexity. The deadline is March 4. The program announcement for the Emerging Models and Technologies for Computation Cluster, which includes quantum and biological computing, is still under development. Also the ITR solicitation has also been posted, with some major changes from previous years.

Donald Knuth's tribute to Robert Floyd highlights the December SIGACT News. Also reviews of a bunch of crypto books, a column on sublinear-time algorithms and the complexity theory column on "Post's Lattice with Applications to Complexity Theory."

In my mailbox yesterday was not one but five copies of SIGACT News shrink-wrapped together. Once I unwrapped them and looked at the labels, only the outer one belonged to me. There were two for other professors in my department, one for our library and one for the library of Loyola University Chicago, which is on the other side of the city. I'm not sure if it was a mistake or some attempt by the ACM to reduce mailing costs, but I hope this is a one-time occurrence.

Show Us Your Papers

I hope you all got your Complexity submissions in on time last week. Now let the rest of the world see your work. Make them into technical reports, put them on your home page, submit them to ECCC and/or CoRR (neither of which conflicts with submitting to Complexity). People won't judge you, okay maybe they will, but no one gets famous by keeping their work a secret.

And since I know you'll ask: I didn't have any Complexity submissions this year. It happens.