Howdy from San Diego

This week I'm at the Federated Computing Research Conference (FCRC), a combination of thirty conferences and workshops with 2200 participants. I'm here for the theory conference (STOC) and Electronic Commerce.

Last night, Adleman, Rivest and Shamir gave their Turing award lecture, each giving twenty minutes of an hour long talk. Their basic them on how cryptology has changed in the last 25 years:

1. Cryptography is now done publicly rather than in secret. This has led to researchers building on each others ideas to create better and better encryption schemes and protocols. But also it has allowed more people to attack these protocols and weed out the bad ones.
2. Cryptography has moved from art to science. Now we have protocols based on mathematical ideas like number theory instead of just creating seemingly complexity functions.

Adi Shamir made other interesting comments like that perfect cryptography is impossible, though very good cryptography can be had at a modest cost. Most attacks on practical implementations of cryptographic protocols work on the implementation as opposed to the protocol.

The lectures were taped and may show up on-line someday. I'll let you know if I find them there--definitely recommended viewing.

Back to Chicago

A personal note: I have accepted an offer to return to the computer science department of the University of Chicago starting this fall. As NEC Labs has been moving its focus away from basic research, it is time for me to go back to an academic life.

I plan to keep this weblog going in Chicago as long as I have things to say.

Foundations of Complexity Lesson 19: The Immerman-Szelepcsenyi Theorem

Previous Lesson

In this lesson we will prove the Immerman-Szelepcsényi Theorem.

Theorem (Immerman-Szelepcsényi): For reasonable s(n)≥ log n, NSPACE(s(n))=co-NSPACE(s(n)).

Let M be a nondeterministic machine using s(n) space. We will create a nondeterministic machine N such that for all inputs x, N(x) accepts if and only if M(x) rejects.

Fix an input x and let s=s(|x|). The total number of configurations of M(x) can be at most c^s for some constant c. Let t=c^s. We can also bound the running time of M(x) by t because any computation path of length more than t must repeat a configuration and thus could be shortened.

Let I be the initial configuration of M(x). Let m be the number of possible configurations reachable from I on some nondeterministic path. Suppose we knew the value of m. We now show how N(x) can correctly determine that M(x) does not accept.

Let r=0
For all nonaccepting configurations C of M(x)
  Try to guess a computation path from I to C
  If found let r=r+1
If r=m then accept o.w. reject

If M(x) accepts then there is some accepting configuration reachable from I so there must be less than m non-accepting configurations reachable from I so N(x) cannot accept. If M(x) rejects then there is no accepting configurations reachable from I so N(x) on some nondeterministic path will find all m nonaccepting paths and accept. The total space is at most O(s) since we are looking only at one configuration at a time.

Of course we cannot assume that we know m. To get m we use an idea called inductive counting. Let m_i be the number of configurations reachable from I in at most i steps. We have m₀=1 and m_t=m. We show how to compute m_i+1 from m_i. Then starting at m₀ we compute m₁ then m₂ all the way up to m_t=m and then run the algorithm above.

Here is the algorithm to nondeterministically compute m_i+1 from m_i.

Let mi+1=0
For all configurations C
  Let b=0, r=0
  For all configurations D
    Guess a path from I to D in at most i steps
    If found
      Let r=r+1
      If D=C or D goes to C in 1 step
        Let b=1
  If r<mi halt and reject
  Let mi+1=mi+1+b

The test that r<m_i guarantees that we have looked at all of the configurations D reachable from I in i steps. If we pass the test each time then we will have correctly computed b to be equal to 1 if C is reachable from I in at most i+1 steps and b equals 0 otherwise.

We are only remembering a constant number of configurations and variables so again the space is bounded by O(s). Since we only need to remember m_i to get m_i+1 we can run the whole algorithm in space O(s).

Open Questions from Hopcroft and Ullman

On page 281 of the 1979 edition the classic theory text of Hopcroft and Ullman lies two tables describing closure and decidability properties of various formal languages. Four entries in the table are labelled by "?" meaning the answer was not known. Those entries are

1. Are context-sensitive languages closed under complementation?
2. If L is context-sensitive is MIN(L) context sensitive? MIN(L) is the set of strings in L who do not have proper prefixes in L.
3. Is it decidable whether the complement of a given context-sensitive language is context-sensitive?
4. Is it decidable whether two given deterministic context-free languages are equal?

We now know the answers to all of these question are "Yes."

1. In 1988, Neil Immerman and Róbert Szelepcsényi independently showed that nondeterministic space is closed under complement. Since CSLs are equivalent to nondeterministic linear space we have that CSLs are also closed under complement. Immerman and Szelepcsényi received the 1995 Gödel Prize for this result. We will cover Immerman-Szelepcsényi in the next Foundations lesson.
2. By using Immerman-Szelepcsényi, one can create a nondeterministic linear time algorithm to check that x is in L and that all proper prefixes of x are not in L.
3. Trivially true by Immerman-Szelepcsényi.
4. This was the hard one. Only in 1997 did Géraud Sénizergues succeed in showing that the problem is decidable. For this work he received the 2002 Gödel Prize. Here is the simplified version of his result, a mere 58 pages.

Computing's Lost Allure?

The New York Times today had an article on the shrinking number of computer science majors in American universities. Let me give you my take on this.

First of all this should be no surprise. People, consciously or unconsciously, follow the money. Computer science majors were a very hot property in the late 90's and now they are less so. So less people are going into computer science.

My advice: Don't follow the money. You will be trying to time the market four years down the road. I remember as an undergrad seeing many of my fellow freshman going into Chemical Engineering because it was a hot area. Four years later many of them had trouble finding or keeping a job and had to move to other areas. Some of them even became.......lawyers.

Best to do what you enjoy. If you enjoy it you will have a better chance to succeed. Worry about the job market when you get there.

Celebration for Walter Savitch

Just got this announcement. And we just discussed Savitch's Theorem in my last Foundations Lesson.

The Department of Computer Science and Engineering at the University of California, San Diego, is sponsoring an event on June 12, 2003, on the occasion of Professor Walt Savitch's birthday and in recognition of his thirty-four years of teaching Computer Science at UCSD. This event will feature two distinguished speakers, Professor Stephen Cook (University of Toronto) and Professor Aravind Joshi (University of Pennsylvania) with a reception in honor of Professor Savitch concluding the program. The event will take place at Eucalyptus Point (Room B) in Thurgood Marshall College on the UCSD campus. Please see the department web site for a link to more information.

This event immediately follows the STOC conference which is also being held in San Diego as part of FCRC.

Turing Machines and Godel's Theorems

A little recursion theory can make Gödel's Theorems intuitively easy.

Let A be the set of <M> such that M does not accept the input <M>. By diagonalization techniques we can show A is not recursively enumerable.

Now let us fix a logical theory like ZFC set theory. The actual theory does not matter much. Let B be the set of <M> such that there is a proof in ZFC of the statement "M does not accept input <M>." B is recursively enumerable since we can just try all possible proofs.

Now B is clearly a subset of A so there must be an input <M> in A-B. For this <M>, we have that M does not accept input <M> but there is no proof of this fact. We now have a true mathematical statement with no proof. This is Gödel's first theorem.

We can be more constructive. Since B is recursively enumerable there is some Turing machine N that computes B. Suppose that N accepts <N>. This means <N> is in B which implies there is a proof that <N> does not accept N, a contradiction.

So <N> cannot accept N which means <N> is not in B. So we have now constructed an N such that the statement "N does not accept <N>" is true but not provable.

But wait a minute, didn't I just give a proof that N does not accept <N>? Actually I had to make the assumption that ZFC is consistent. If ZFC is inconsistent then every statement (true or false) is provable so B would not be a subset of A and my whole argument falls apart.

If ZFC could prove that ZFC is consistent then I would not have to make any assumption and would have a contradiction. Thus ZFC cannot prove its own consistency. This is Gödel's second theorem.

Logicians tell me I'm cheating: I had to assume something technically stronger than consistency for this argument to work. Still these proofs illustrate the amazing power of Turing machines to make Gödel's theorems easier to understand.

Foundations of Complexity Lesson 18: Savitch's Theorem

Previous Lesson | Next Lesson

Unlike what we believe for time, there is a polynomial relation between deterministic and nondeterministic space.

Savitch's Theorem (1970): NSPACE(s(n)) is contained in DSPACE(s²(n))

Proof: Recall the definition of tableau (as described in Lesson 12). Let N be a nondeterministic machine that uses s(n) space. We can represent the computation of an input x of length n by a tableau where each configuration has size O(s(n)) and there are at most m = c^s(n) configurations for some constant c.

We will create a deterministic machine M(x) to determine whether the tableau is proper and thus N(x) accepts. First we need a subroutine CHECK to determine whether one configuration can reach another in 2^t steps. We do not have enough space to write the entire tableau but instead we do a divide and conquer approach: Try all possible middle configurations and recurse on each half.

CHECK(CONF1,CONF2,t)
\* Output TRUE if CONF1 can get to CONF2 in at most 2t steps *\
If t=0 then 
        {if (CONF1 = CONF2
         or CONF1 goes to CONF2 in one step on machine N)
         then output TRUE else output FALSE}
For each CONF
  {If CHECK(CONF1,CONF,t-1) and CHECK(CONF,CONF2,t-1) then output TRUE}
Output FALSE

We can implement CHECK by only having to store a constant number of configurations at each level of the recursion with a recursive depth of t for a total space of O(ts(n)).

Let CONF₀ be the initial configuration encoding x. We can now give our main routine.

MAIN
Let r be the smallest integer at least log2(cs(n))
For each CONF in an accepting state
   {If CHECK(CONF0,CONF,r) then output TRUE}
Output FALSE

Total space used: O(log₂(c^s(n))s(n)) = O(s²(n)).

The Nerd Shot

Many years ago I was commuting home on the train with my wife and one of her colleagues. I showed them the group picture from a Dagstuhl I had attended that they recently sent me. My wife and her friend spent much of the train ride laughing at the collection of nerdly looking people in the photo. Ever since then we have jokingly called a conference group picture the nerd shot.

Computer scientists, especially in Europe, love to take pictures of other computer scientists. Problem is computer scientists are not particularly photogenic nor, for the most part, are they good photographers. The worst is the group photo, where we are herded like cattle to some enclosed place where we stand until all the strays are rounded up and finally the photo is taken, sometimes several times by several people.

Some things have changed over time. Most photos are now taken digitally and get posted quickly, sometimes before the conference is over. My kids enjoy playing "Where's Daddy?" especially if I am out of town. But still the group photo experience remains the same.

I was talking to my wife on the phone at the last Dagstuhl and told her it was time for the nerd shot. She said I should fix my hair and I replied "What? You want me to stand out?"

Without further adieu here is that nerd shot.

Foundations of Complexity Lesson 17: Space Complexity

Previous Lesson | Next Lesson

In addition to time, computer scientists also worry about the memory or space that a Turing machine uses. Roughly one can measure space as the number of tape squares used by at Turing machine. We would like to talk about space bounds like log n and still be able to read the whole input so we need a slightly different model.

We now allow our Turing machine to have a read-only input tape, one or more work tapes and for a Turing machine computing a function, a write-only output tape. On the input tape the head can move back and forth but it cannot change the values in any cell. On the output tape the head can only move right, writing as it moves. The amount of space a Turing machine uses on input x is the number of cells of the work tape that it uses. We will assume a space bound of at least log n since we need log n bits to describe the location of the the input head pointer.

In real world terms, think of your computer accessing "the internet". You can still reach many pages even though you cannot store the entire internet on your computer.

Any machine that runs in time t(n) clearly also runs in space t(n). If a machine uses space s(n) and it halts then it will halt in time c^s(n) for some constant c. Otherwise the machine will repeat a configuration and run forever.

We define the classes DSPACE(s(n)) as the set of languages that are accepted by Turing machines using at most O(s(n)) space. NSPACE(s(n)) is the same for nondeterministic machine. We will always assume s(n)≥log n and s(n) is an easily computable function.

Common space classes include L=DSPACE(log n), NL=NSPACE(log n), PSPACE=∪_kDSPACE(n^k) and NPSPACE=∪_kNSPACE(n^k).

Unlike the P versus NP question, we know quite a bit about the relationship of deterministic versus nondeterministic space through the following two results.

• Savitch's Theorem: NSPACE(s(n))⊆DSPACE(s²(n)). In particular this means NPSPACE = PSPACE.
• Immerman-Szelepcsényi Theorem: If L is in NSPACE(s(n)) then the complement of L is also in NSPACE(s(n)).

We will discuss these theorems in more detail in upcoming lessons.

Universal Search

Psst. Want to know the fastest algorithm for factoring? I can give you an algorithm that is within a constant multiplicative factor of the best possible factoring algorithms.

Actually this is an idea due to Levin. Let p₁, p₂, ... be a list of all programs. On some input m simulate program p₁ for half of your computation time, p₂ for a quarter of the time, p₃ for an eighth of the time, etc., until one of these programs outputs a factor of m. If p_i is the fastest algorithm for factoring then our algorithm will run in time at most 2ⁱ times the running time of p_i. The multiplicative factor 2ⁱ is independent of m but unfortunately could be quite large.

Marcus Hutter gives another algorithm that has a multiplicative factor of 5 but has a large additive constant. The trick is to spend some of your time searching for a proof that an algorithm is correct and runs in certain amount of time. You then only need to simulate the provably fastest algorithm found so far.

Hutter's algorithm works only as fast as the provably best algorithm with a provable running time. It could very well be the case that there is some good heuristic for factoring that does not have a provable running time or proof of correctness. Levin's technique will capture this case.

Of course, neither of these papers gives a practical algorithm as the constants involved go beyond huge. Nevertheless it is still interesting to see the theoretical possibilities of universal search.

FCRC

Even the largest theoretical computer science conferences draw at most a couple of hundred people. Many (but not all) other areas of computer science also do not draw large numbers of participants. To have a larger and more noticeable conference and possibly to get press attention, the CS community decided to hold a joint conference covering many different areas in computer science. In 1993, the first Federated Computing Research Conference was held in San Diego.

The press didn't show but with some cross-collaboration the conference was considered a mild success. After stops in Philadelphia and Atlanta, FCRC returns to San Diego June 7-14. The 2003 FCRC includes the main spring theory conference (STOC), Electronic Commerce (EC), Computational Geometry, Principle and Practice of Parallel Programming and many others. Registration deadline is May 7.

For the first time the Complexity Conference will not be part of FCRC as 2003 is a Europe year for us. I am planning to attend FCRC for STOC and the EC meeting. If you attend FCRC stop by and say hi.

History's Loss/Mathematics' Gain

Some excitement at Schloss Dagstuhl this week. Localized high winds tore the metal plating off the roof of much of the new building Wednesday evening. Much of that roof sits in the courtyard--quite a sight. The good news is no one was injured and property damage, besides the roof, was minimal. A few of us had to switch rooms but the workshop goes on.

Let me finish off this centennial week with a story of Kolmogorov that I have heard from different sources so some variation of this story is likely true. Kolmogorov initially wanted to be an historian. He looked at the question as to whether taxes in Russia in the middle-ages were collected at the house level or at the village level. He analyzed tax data and showed that that data had a much simpler description if taxes were collected at the village level. (You can see the seeds of Kolmogorov complexity here). He presented these results to the history faculty to great applause. Asking them whether he could publish such a paper he was told, "You only have one proof. You cannot publish in a history journal without at least two more proofs of your hypothesis." And so Kolmogorov left history for a field where one proof suffices.

The Power of Random Strings

Let R be the set of random strings, the x such that C(x)≥|x|. There are various theorems that many such x must exist at every length. What is the power of R?

R is co-r.e. as one can enumerate small programs to generate the strings x such that C(x)<|x|. One can also reduce the halting problem to R: Suppose we want to know whether a program p halts on blank tape. Let n=|p|. Let t be the number of steps to enumerate all of the strings in R of length 2n. We know when we have enumerated them all by using R. Then if p halts it will halt within t steps. Otherwise let s>t be the number of steps p needs to halt. We can run the enumeration of strings in R of length 2n for s steps. Let x be the lexicographically least string of length 2n not enumerated. We have C(x)≤|p|+O(1) since we need only p to describe this process. But since |p|<2n=|x| this contradicts the fact that we had enumerated all the nonrandom strings.

In this workshop Eric Allender talked about his work with various colleagues looking at what one can get with polynomial-time reductions to random strings. The reduction time above is not bounded by any recursive function. For example they can show any language in PSPACE polynomial-time reduces to R and any language in EXP reduces to R via polynomial-size circuits, as well as many results on different notions of random strings. They use various complexity tools like pseudorandom generators and interactive proof systems in their proofs.

More on Kolmogorov Complexity

There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but you might find it at the bottom of Sophie Laplante's web page). Reading the cartoon you might find it funny because not all strings seem equally random even if they are equally likely. Kolmogorov formalized this idea by measuring the randomness of a string x, denoted C(x), by the smallest program that generates x.

At this Dagstuhl workshop there are many talk on a number of variations of Kolmogorov complexity. John Tromp had a nice presentation on the basic notion. He showed, among other things, that for any x you can find a constant length y such that C(xy)>C(x). This seems obvious but it is pretty tricky tor prove. Tromp's proof works by defining a new C-based measure on strings and using that to show that any string x has a small number of programs generating x that have length close to C(x) and using that fact to get his result. He doesn't have a write-up yet, but I'll keep a lookout for it.

Kolmogorov Centennial

Andrei Kolmogorov was born exactly hundred years ago last Friday the 25th. Kolmogorov made major contributions to "every mathematical area except number theory" as many a Russian have put it. He has directly affected my research through his algorithmic study of randomness, an area we now call Kolmogorov complexity.

To celebrate the centennial, I'm back in Dagstuhl for a workshop on Kolmogorov complexity after a brief stop in Heidelberg. Most of the best researchers in the area are here including many Russians. It should be an exciting week all around and during the week I will post some of the interesting work that I hear about.

For a background on Kolmogorov complexity, here are some lecture notes from a short course I gave. For an in-depth study, I cannot recommend enough the Kolmogorov Complexity book of Li and Vitanyi.

Complexity Classes of the Week: SBP and A0PP

Previous CCW

Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's take a look.

Böhler, Glaßer and Meister present a new class SBP that can be defined as follows. A language L is in SBP if there is a #P function f and an FP function g such that for all x,

1. if x is in L then f(x)>g(x), and
2. if x is not in L then 0≤f(x)<g(x)/2.

Vyalyi introduces a class A₀PP which has exactly the same definition except #P is replaced by Gap-P. [If I lose you in alphabet soup in this post, you can use the zoo to keep up.]

In both classes the "2" in the definition can be replaced by 2^|x|k for any fixed k.

SBP sits between MA and AM, a rare natural class between these two. SBP is also contained in BPP_path but there is a relativized world where it is not contained in Σ₂, giving a relativized answer to the open question in my CCW on BPP_path. SBP is closed under union but whether it is closed under intersection remains open even in relativized worlds.

QMA, the quantum version of MA, is contained in A₀PP, which itself is contained in PP. If A₀PP = PP then PH is in PP. He claims this gives evidence that QMA is not PP but given strong pseudorandom function, PH is in PP. But co-NP is probably not in QMA which is evidence enough for me that QMA is not equal to PP.

To prove his later result, Vyalyi notes that P^#P[1] is in SPP^C₌P and he shows that SPP^A₀PP is contained in PP and his result follows since C₌P is in PP and by Toda's Theorem PH is in P^#P[1].

Paddable NP-Complete Sets are Isomorphic

By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof builds on an old result of Myhill that all r.e.-complete sets are recursively isomorphic. Since nearly all natural NP-complete sets are paddable then they are also isomorphic.

First some definitions:

• A set A is paddable if there is a polytime computable function p:Σ^*×Σ^*→Σ^* such that
  1. For all x and y, x is in A if and only if p(x,y) is in A.
  2. p is 1-1 and |p(x,y)|>|x|+|y|.
  3. p is computable in polynomial-time.
  4. p is invertible on its range in polynomial-time.
• Sets A and B are isomorphic if there is a reduction u from A to B such that
  1. u is a reduction: For all x, x is in A if and only if u(x) is in B.
  2. u is 1-1 and onto.
  3. u and its inverse are both computable in polynomial time.

Suppose A and B are paddable NP-complete sets. Let f reduce A to B and g reduce B to A. Let p be a padding function for A and q a padding function for B. Let r(x)=q(f(x),x) and s(y)=p(g(y),y). The function r is a 1-1 length-increasing efficiently-invertible-on-its-range reduction from A to B and s is the same from B to A.

Now we can define our isomorphism u(x) from A to B.

• If x is not in the range of s then let u(x)=r(x).
• If x is in the range of s, let y be such that s(y)=x.
• If y is not in the range of r then let u(x)=y.
• If y is in the range of r, let z be such that r(z)=y.
• Recursively compute u(z).
• If u(z)=y then let u(x)=r(x) otherwise let u(x)=y.

Since r and s are length-increasing, the depth of the recursion is at most the length of x so u is computable in polynomial time. I'll leave it to the reader to verify that u is an isomorphism.

The Turing Award

As noted in a comment to the last post, it is now official that Ron Rivest, Adi Shamir and Len Adleman won the 2002 Turing Award.

Unfortunately outside of computer science and particularly outside academics the Turing award is not so well known or respected. In 1987, I was a graduate student visiting my old fraternity at Cornell, Anne Marie Hopcroft came in. Anne Marie was dating one of the fraternity brothers at the time. "My father won the Turing Award! My father won the Turing Award!", she exclaimed. Nobody, besides myself, seemed the least bit interested. She and I tried to explain the importance of the award but to no avail. Had her father won the Nobel prize, you could be sure the reaction would have been different.

The 1997 movie Good Will Hunting gave great publicity for mathematics much by explaining the importance of the Fields Medal to the masses. What can we do to make the Turing Award better known?

Awards

The ACM doctoral dissertation award, given to the best doctoral thesis in computer science, was awarded to Venkatesan Guruswami for his thesis "List-Decoding on Error-Correcting Codes". Another theorist, Tim Roughgarden, was one of the runners-up. This was definitely a great year for theory Ph.D. theses.

Rumors are flying that theorists Ron Rivest, Adi Shami and Len Adleman won the Turing Award for their work on the RSA cryptosystem. The Turing Award is the highest honor in computer science, the closest we have to a Nobel prize.