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.

Critical Mass

In the left column of this weblog's homepage, I've added a new "weblogs" section to list the academic weblogs that I have been following. Not very long right now, so start up a relevant weblog and I'll add you to the list.

What is Critical Mass? This is a weblog written by U. Penn English Professor Erin O'Connor. Not much computer science but she covers a number of issues about academic freedom, an important issue to every academic. Take a look.

Don't forget that the 2004 Complexity Conference submissions are due today. Have a great Thanksgiving!

Theory and XML

XML (eXtensible Markup Language) has become quite a popular data format in recent years. XML roughly corresponds to a tree. For example,

<person><name>Harry</name><age>29</age></person>
<person><name>Jane</name><major>Computer Science</major></person>

represents a tree. The root having two children, each labeled "person". The first of these children has two children named "name" and "age". The first of those children has a leaf node labeled with the phrase "Harry". For a larger example, see the RSS feed for my weblog.

XML was designed as a flexible way to present documents for later displaying. Since the XML format can be easily produced and parsed, XML also serves as a standardized method for transferring data between databases, far better than the old CSV (Comma-Separated Values) format.

Recently there have been some work on directly manipulating and querying the XML data. As a theorist, this seems like a bad idea, particularly for larger databases. While XML completely represents the underlying tree, it is not a good implementation of that tree. Basic tree operations like parent and sibling are very expensive just looking at XML. About the only thing one can do quickly with XML is depth-first search. Far better to "shred" the data into a better tree implementation like a DOM (Document Object Model) or a full-fledged database and do the work there, rewriting a new XML if needed.

One issue though is when the XML file is on the order of 5-10 GB, a bit larger than what can be stored in the memory of a typical desktop machine. One can stream through the file rather quickly but cannot recreate the tree. This opens up some interesting theoretical questions:

1. Given a stream of data in XML format, how can one do efficient analysis and manipulations of the underlying tree? I suspect one would want to sometimes shred subtrees, but you cannot determine the size of the subtree until after its been streamed. Perhaps some randomness or streaming the file multiple times might be helpful.
2. XML might not be the right model of a tree for this purpose. What is the best way to stream a tree or other data structure to allow an efficient implementation of the basic operations of the data structure? Perhaps some redundancy might be useful.

Rational Functions and Decision-Tree Complexity

I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them:

Let f:{0,1}ⁿ→{0,1}. Let h and g be n-variable degree d polynomials over the reals. Suppose for all x in {0,1}ⁿ, g(x)≠0 and f(x)=h(x)/g(x). Is there a constant k such that the decision-tree complexity of f is bounded by d^k?

The decision-tree (or query) complexity is the number of bits of x that need to be viewed to determine f(x). The queries to the bits of x can be adaptive. I'm particularly interested in the case where d is poly-logarithmic in n.

Nisan and Szegedy answer the question in the affirmative if g(x)=1. Their result holds even if f(x) is only approximated by h(x). However if we allow arbitrary g(x), h(x)/g(x) can closely approximate the OR function which requires looking at all of the bits. The case where we require exact equality of f(x) and h(x)/g(x) is the open question at hand.

Update 1/14/26: Solved!

Midwest Theory Day

Over the years a number of localized theory workshops have developed which bring together researchers from around the area to mingle and learn about some of their research. For example BATS (Bay Area Theory Seminar-San Francisco area), CATS (Capital Area Theory Seminar-Washington DC), DIMACS Mixers (New Jersey), Netherlands Theoriedag and others including many I've never heard of.

In the middle of America we have the Midwest Theory Day. Generally since 1980 this is a day of talks held in the fall in the Chicago area and in the spring somewhere else in the Midwest such as the University of Wisconsin, Indiana, Illinois, Purdue, Notre Dame, etc. The next Midwest theory day will be held December 13 at DePaul University and in the spring on April 24 at the University of Iowa.

So come to Chicago or attend (or organize) you own local area theory seminar and meet your theory neighbors.

Editors Needed

Back in my science-fiction reading days, I particularly remember one editorial written in one of those anthology magazines about 1980: In the near future, you will be able to access, via your personal computer, any science fiction story right after it has been written. If you like a certain author, you can read other stories from that author, even if we didn't decide to put it in this magazine. In this future world, will you still need me, the editor? The answer is yes, for there will be way too much dreck out there for you to find the good stories within, and you will need people like me to point them out to you.

The future is now and though I haven't kept up with science fiction, the same issue applies to academic publications. Recent posts by Michael Nielsen and on Slashdot have asked: With nearly all new papers in physics and computer science easily accessible on the web, how do you find the ones worth reading?

Conferences have traditionally played this role in computer science. But, by definition, paper choices are decisions by committee and with the massive growth in the field, many good papers do not appear in the major conferences.

What we need are "editors"! You can help. Write a survey paper, or spend a page in your research papers discussing the important earlier results in a field. Maintain a web page pointing to papers you find interesting. Start a weblog saying what you find interesting--you don't have to post long or often, just to say, hey, this paper is worth looking at. This way people with similar interests to you can find out what at least you think is important. Only by many of us working together can we make the interesting papers stand out.

A Regular Problem

Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m≥0, x^m is in A} Simon asked, as a homework problem, to show that if A is regular then L(A) is also regular. The standard solutions require an exponential increase in the number of states. Simon asks whether this is needed in general. If A is accepted by an n-state DFA, can one find a poly(n)-state DFA for L(A) or is an exponential state DFA for L(A) required?

As an aside the submission deadline for the Complexity Conference is right around the corner. Get your papers ready.

Opportunities at Chicago (Blatant Plug)

[I will do this just once. Feel free to use the comments link to mention your own institution.]

We are seeking theory graduate students and faculty (all ranks) in the Computer Science Department of the University of Chicago. The Toyota Technological Institute, located on the University of Chicago campus, is looking for both faculty and postdoctoral candidates.

The Theory Group has expanded over the past few years and will continue to grow. We have a long tradition of outstanding doctoral students and notable research accomplishments.

Click here for further information.

25 Years of Science Times

It happened right after I started high school in suburban New Jersey, the start of the Science Times section in Tuesday's New York Times. The Science Times not only helped get me excited about science but made me feel others could get excited over science as well. I've kept reading it off and on during these past 25 years. The Science Times has reported on a fair amount of research in complexity and theoretical computer science, for a time some joked that a result was not important until it appeared in the New York Times.

Today the New York Times celebrates the 25th Anniversary Issue of the Science Times. It features 25 questions such as Does Science Matter? and What Is the Most Important Problem in Math Today? (Hint: It's not P versus NP).

I'll end this post with a quote from the essay of Alan Lightman:
All of the scientists I've known have at least one quality in common: they do what they do because they love it, and because they cannot imagine doing anything else. In a sense, this is the real reason a scientist does science. Because the scientist must. Such a compulsion is both blessing and burden. A blessing because the creative life, in any endeavor, is a gift filled with beauty and not given to everyone, a burden because the call is unrelenting and can drown out the rest of life.

CISE Reorganization

The Computer and Information Science and Engineering Directorate of the NSF has completed it reorganization. The CISE web site details the new structure.

CISE now has four divisions. Instead of each division have a large number of specific programs, each division contains a smaller number of clusters covering a broader research area. I'm happy to see "Computational Complexity" specifically mentioned in the Formal and Mathematical Foundations Cluster in the Division of Computing & Communication Foundations. However it shares that cluster with such diverse topics as "computational algorithms for high-end scientific and engineering applications" and "analysis of images, video, and multimedia information." Hopefully funding panels will meet in the more specific areas to avoid trying to compare proposals from vastly different areas of computer science.

Quantum and Biological Computing sit in a different CCF cluster, Emerging Models and Technologies for Computation. This shows NSF's hopes for these new technologies but may also give them a way to phase out these areas if the technologies don't show promise.

Program announcements for the CCF clusters are still under development. The ITR solicitation is still not expected until Thanksgiving. So if you plan a grant proposal this year, you'll still need to wait.

The Web and Research

I received the following email from David Molnar, a Berkeley graduate student. He asks some interesting questions about the use of the web and research. Instead of just answering them immediately, I though I would share his email (with his permission) and let you think about it. Feel free to comment. I'll also address some of his points later in future posts.

Molnar's Letter:

I wanted to follow up on your comment about theoretical computer science and e-mail/IM. Also, use of weblogs.

1. There's a piece of folklore about how IP=PSPACE was proved pursuant to some race between many researchers carried out over e-mail. I've once or twice found myself in e-mail races with other people on mailing lists when we're responding to something technical. Do you think the day will come when some major theorem is proved in an IM chat room? :)

2. Weblogs as place for ideas. A friend of mine asked me if I thought researchers in theory would be interested in putting up a web page (actually, we were discussing a wiki) about open problems. My response was pretty much like what you see in Oded Goldreich's FAQ -- "well that's nice, but good research problems are hard to find, and people seem to reserve them for themselves or their close colleagues."

   The point: I find that I'm starting to use my weblog as a place to deposit ideas for problems that I just don't have time to pursue, or aren't in what I think is my main line of research. In the old days they would have gone into a notebook somewhere and no one would have seen them. Now maybe someone will pick them up -- and I think that's great (especially since I usually don't know how to progress). At the same time, I wonder how peoples' concerns about ownership of ideas will affect the way they use weblogs. What do you think?

The PCP Theorem

This week I started teaching the PCP theorem: Every language in NP has a proof that can be probabilistically checked with only O(log n) random coins and a constant number of queries. One graduate student asked me which came first, the PCP theorem or the connection to hardness of approximation. That seemed like a strange question; after all why would so much effort be put into reducing parameters like number of random coins or queries unless there was some application behind it. But then again, so much emphasis is now in the literature on these parameters that he probably thought these were always the parameters people cared about the most.

To put the record straight: Feige, Goldwasser, Lovász, Safra and Szegedy made the connection between the interactive proof literature and approximation. Arora and Safra showed the importance of reducing random coins and queries and proved a weaker version of the PCP theorem. The theorem in the above form was proved by Arora, Lund, Motwani, Sudan and Szegedy.

I have been teaching off the notes of Madhu Sudan from a short course he taught on the PCP theorem. The notes don't go through every detail, but they give one of the better expositions of what is still quite a complex proof.

What happened at NEC?

The NEC Research Institute (NECI) died just over a year ago. I didn't feel comfortable talking about it then so let me say a few words now.

I joined NECI in 1999 just after its tenth anniversary. When I joined its mission and focus was basic research in computer science and physics. NECI gave me considerable time and resources to study fundamental questions in computational complexity. It was an exciting place to be.

Soon thereafter some changes were occurring. NEC modified the mission of NECI to focus on producing technologies with basic research secondary. Some researchers (though not us theorists) were encouraged to join "technology groups" to find practical applications of their research. But during this time, the administrators always supported basic research and I never felt uncomfortable doing theory.

But then on November 1, 2002, NECI merged with NEC CCR&L, a more applied research lab in the same building to form NEC Laboratories America. The new mission makes no mention of basic research. The scientists in charge were replaced by engineering/management types. Many of the research scientists, particularly physicists, were let go.

My job was never in immediate danger but NEC was no longer the place for me and so I went on the job market; no one was surprised when I decided to leave.

A corporation like NEC needs to make decisions for the health of the company. I do not fault NEC for the decisions that it made and they gave me a few great years. Still I mourn the NEC Research Institute, quite a special place during its thirteen year run.

Lessons from the IM Experiment

Last week I started an experiment using instant messaging. I thank the many of you who sent me IMs, a great way for me to meet you, the readers of this weblog. I plan to keep trying IM for a while but I have had learned a few lessons which seem obvious in retrospect.

Instant messaging can be a time sink. I love communicating with people, which is the main reason I keep this weblog going. However, as most academics, I have much going on and can't afford to have many lengthy discussions. I've also learned there is no clean way to end an IM conversation. So please feel free to IM me but don't take it personally if I rudely keep the conversation short.

Just because the nice icon on the home page says I'm online it doesn't mean that I am at my computer and available to chat at the moment. Often I am and I will but if not I will eventually see your message and respond. If there is really is something important that you want to discuss with me via IM we can setup a scheduled time via email. I often do this with phone calls so why not IM too?

I've also discovered IM conversations can be recorded, posted on the web and could be used in a court of law. I need to be careful about what I say.

I have already had some interesting research conversations and ideas for weblog posts via IM. The last post came in part because of some IM questions about the Feigenbaum-Fortnow paper. Email became a powerful research tool when email use hit a critical mass among computer scientists sometime in the mid-late 80's. I believe IM will also follow that curve and I hope to keep ahead of it and perhaps nudge it a little bit.

Changing Strings but not Distributions

Let f be a function that maps Σⁿ to Σⁿ. Let U represent the uniform distribution on Σⁿ and D be the distribution that one gets by applying f to a string drawn from U.

We wish to find f that change x but keep the underlying distribution close to the same, in particular we want the following properties,
(1) Prob(f(x)≠x)≥2/3 when x is drawn from U.
(2) U and D should be statistically close, informally no algorithm making a polynomial number of samples will be able to distinguish, with high confidence, whether those samples came from D or U.

Achieving such an f is easy, consider f that just flips the first bit of x. (1) holds all the time and U=D.

Suppose we add a restriction to f:
(3) In the bits where x and f(x) differ those bits are 1 in x and 0 in f(x). For example, f(011)=010 is allowed, but f(011)=f(111) is not.

An f fulfilling (1), (2) and (3) is impossible. (1) and (3) means that f will reduce the number of ones on most of the strings and taking say n³ samples we will notice a statistical difference in the number of bits which are 1 depending on whether the samples were drawn from U or D.

Suppose we replaced (3) with a weaker restriction:
(3') In the first bit where x and f(x) differ, that bit is 1 in x an 0 in f(x). So f(110)=011 is allowed but f(001)=010 is not allowed.

Can an f fulfilling (1), (2) and (3') exist? Not so clear, but Peter Shor found a simple example: f(0ⁿ)=0ⁿ, and for the other x, f(x)=x-1 where x is viewed as a nonnegative integer written in binary. D is indistinguishable from U yet f changes nearly every string.

These questions are related to an old paper I had with Joan Feigenbaum which has gotten some recent attention because of a nice new FOCS paper by Bogdanov and Trevisan that builds on our paper. The proofs in these papers work partly because (1), (2) and (3) cannot all happen even for arbitrary distributions U. Both papers give a negative result for a nonadaptive case; the adaptive case corresponds to (1), (2) and (3') and Shor's example shows that the proof techniques will not directly lead to a solution in the adaptive case which remain open.

Quantum Leaping to Conclusions

A quantum computing graduate student sent me email over the weekend. He had thought he had proven some surprising results about the class PP and was wondering if he was making some mistake. After some discussion here was his reply:

Ok I get it. Somehow I jumped to the conclusion that P^PP was PP.
There is one more for your blog: A⊆ B implies B⊆ A^B but not A^B⊆ B (duh!)

He goes on to say he made his quantum leap to conclusions since for the quantum class BQP, P^BQP=BQP, he thought the same property must hold for all classes.

I present this because he suggested it for my weblog and as a public service for those who might make a similar mistake. Yes, in case you were wondering, for reasonable classes A (like A=P), B⊆A^B without needing to assume A⊆B.

When Good Theorems Have Bad Proofs

Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem.

Theorem: If NP is in BPP then the whole polynomial-time hierarchy is in BPP.

Let's focus on simply showing Σ₂ is in BPP if NP is in BPP. The rest is straightforward induction. Here is our first proof:

Σ₂=NP^NP⊆ NP^BPP⊆BPP^BPP=BPP. Do you see the problem with this proof?

To get a correct proof (first due to Zachos) we need to use Arthur Merlin games. Consider a Σ₂ language L as an ∃∀ expression. Since NP is in BPP, we can replace the ∀ with a probabilistic test. This gives us what is known as MA or a Merlin-Arthur game where the powerful Merlin sends a message that Arthur can probabilistically verify. A now classic result shows that MA is contained in AM, where Arthur provides a random string to Merlin who must then provide a proof based on that string. Once again we apply the NP in BPP assumption to allow Arthur to simulate Merlin probabilistically and now we have a BPP algorithm for L.

The problem in the first proof is in the second "⊆". The assumption NP in BPP does not imply NP^A in BPP^A for all A.

Talk to Me

How has the internet most affected the study of science? In one word: communication: the ability for scientists to discuss and share their research with each other quickly and cheaply. So I strive to find new ways to use the internet to improve communication. Starting this weblog is one such example. I'd thought I would try another: Instant Messaging.

Now many of you are thinking I am crazy, but for different reasons. Some of you out there have been using instant messaging for years and wondering how I could consider it s "new" technology. But many of you out there have barely figured out how to read your email attachments and have hardly even heard of IM.

On a trial basis, for my weblog readers, I will welcome your instant messages. Talk to me about this weblog, about complexity and computer science in general or about whatever you want. Maybe I'll start a trend and all computer scientists will IM each other. Maybe not but it's worth trying out.

I'm using Yahoo Instant Messaging; my Yahoo id is the imaginative "fortnow" (note: I do not read email sent to fortnow@yahoo.com). I put a button on the left column of the weblog home page that tells you when I am online and you can click to connect. I look forward to hearing from you.

What's happening at the NSF?

There is a big reorganization in the CISE directorate of NSF. To understand what's happening, let's review the previous structure..

The National Science Foundation, like most government bureaucracies, has a tree-like structure. At top is the office of the director (Rita Colwell). Below that are several directorates including the Directorate for Computer and Information Science and Engineering (CISE) headed by Peter Freeman. By law every organization in NSF cannot be just "science" but "science and engineering" except for the Foundation itself.

Below CISE were several divisions, including Computer-Communications Research (C-CR) headed by Kamal Abdali. C-CR ha several programs including the Theory program headed by Ding-Zhu Du.

Peter Freeman, who recently became head of CISE, has decided to reorganize the whole directorate. Exactly what it will become should be announced next week but there are some hints in this presentation. Change is always scary but I'm hopeful theory will survive. I'll give more details when I know them.

To overcome the tree structure of NSF, there are a number of cross-disciplinary programs. One such program, Information and Technology Research (ITR), has produced several large, medium and small grants to a variety of projects, including many applications of theory. This is the last year of ITR solicitations and the calls have been well behind schedule, probably not unrelated to the CISE reorganization. This year's topic will be on "ITR for National Priorities" with more details promised by Thanksgiving. Unconfirmed rumors have the program will be more focused and only making medium sized grants.

TTI

There are two computer science departments on the University of Chicago campus. The one I belong to, a department in the physical sciences division of the University and the other, the Toyota Technological Institute at Chicago (TTI-C). What is TTI-C?

The Toyota Technological Institute, a university covering various engineering disciplines located in Nagoya City, Japan, was founded in 1981 from funds from the Toyota Motor Corporation as directed by the Toyoda family. They decided to start a computer science department and locate it in the states to have a broader access to computer science faculty and students. For various reasons they settled on Chicago and set up an agreement with the University of Chicago, using space in the University of Chicago Press building. TTI-C has just officially started up and have already signed up a few strong faculty members including theorist Adam Kalai and Fields medalist Stephen Smale. TTI-C plans to increase its faculty size and start up a graduate program in the near future.

Although there will be some sharing of courses and a few of our faculty (including myself) sit on a Local Academic Advisory Council for TTI-C, TTI-C will formally maintain itself as a separate institution from the University. Nevertheless close collaborations between our department and TTI-C has already established an exciting research environment for our combined faculty and students.

The Agony of Defeat

This is for my friends in Boston who suggested I do a sports post.

One of the great parts of my job is working with people from around the world. I was working with a graduate student, Luis Antunes, from Portugal when we found out that Portugal would play the US in the 2002 World Cup. We had various rounds of taunting back and forth with me fully knowing the US didn't stand a chance in that match. When the US did win, Luis tells me the whole country went into a deep depression. By contrast, for the most part people in the US didn't care.

I can now understand Portugal's pain as the city of Chicago has gone into a similar kind of quiet depression over the Cubs failure to advance to the world series. Impressive what sports can do to the psyche of a city or a country.

Memo to my friends in Boston: Hope things go well for the Sox so your city doesn't end up feeling tomorrow like Chicago does today.

Tutorials on Machine Learning and Mixing via Markov Chains

Just prior to the FOCS conference, Avrim Blum gave a tutorial on machine learning and Dana Randall gave a tutorial on mixing. As the talks were computerized, even if you, like me, missed the conference, you can view Blum's slides here and Randall's slides here. Randall also has a companion paper that appeared in the proceedings.

Eli Upfal also gave a tutorial on Performance Analysis of Dynamic Network Processes which I haven't found online yet.

Columbus Day

Today is Columbus Day, a minor holiday in the states. There is a great saying about Columbus: He is not famous for being the first person to discover America, rather he is famous for being the last person to discover America.

The same principle holds for proving theorems. Think about it.

Advice for Students Going to a Conference

With FOCS starting this weekend, here is some advice for students attending a conference.

What is the purpose of a conference? Disseminating information is the obvious answer, but there are better ways these days to announce new results. No, the major reason for conferences is to bring a large segment of our community together in one place. Keeping that in mind,

• Meet People: Don't just hang out with students from your own department. Talk to other students, they will be your future colleagues. Don't be intimidated by senior people whose names you have seen on famous papers. Deep down they are just like you.
• Don't go to too many talks: You will burn out and not remember much of anything. And too much time in talks detracts from the main purpose of the conference. Pick and choose your talks based on your research interests, the abstracts in the proceedings and those given by someone with a reputation for giving good talks.
• Go to the business meeting: It will give you a flavor of the inner workings of the theory community. With luck there will be a lively discussion of some arcane issue. And don't forget the free beer.

Remember, networking is as important in academics as it is in business. But perhaps the most important piece of advice I can give: Have fun.

FOCS

Next week is the 44th FOCS Conference in Boston. FOCS, the Symposium on the Foundations of Computer Science is, with STOC, one of the two major American general theory conferences. Okay, usually American. STOC was in Crete in 2001 and FOCS will be in Rome next year but the other 77 FOCS and STOC conferences were held in North America.

I won't be attending the FOCS conference this year, but will definitely be at the next STOC being held in Chicago. I'll likely ask a grad student to pick me up a FOCS proceedings. I'm not sure why; most of the papers are available on-line, the proceedings take up valuable bookshelf space and I've barely opened the proceedings of the last few conferences. But I have a complete set of STOC, FOCS and Complexity proceedings going back to 1986 and I'm a sucker for tradition.

A New Genius

While on the topic of awards, we have a new "genius" in the theoretical computer science community. Computational geometer Erik Demaine just received a MacArthur Fellowship. Congrats!

Waiting for Nobel

The Nobel science prizes will be awarded next week: Medicine on Monday, Physics on Tuesday and Chemistry and Economics on Wednesday. Nothing against the Turing Award and Fields Medal but it is the Nobel that is a household name. Given the increasing connections between computer science and the other sciences, you never know who you might know who might win.

On the Nobel home page one can find some interesting articles on life as a scientist by some Nobel Laureates. Paul Samuelson ends his story with "Always I have been overpaid to do what has been pure fun," which nails the point that the most important requirement to being a successful researcher is to have fun doing it.

Happy Fiscal New Year

I have tried to keep politics out of this weblog with the exception of issues related to science, in particular science funding and immigration. To celebrate America's fiscal new year, let's talk about immigration.

Congress has declined to renew the higher annual cap on H1-B visas, rolling them back to 65,000 for the fiscal year starting today from 195,000 in 2000. H1-B's allow "employers to hire foreign workers with special skills they can't find among American job applicants," typically for high-tech jobs. But H1-B's are also used for visiting researchers at industrial research labs and some university positions. When the limit is reached, the government will no longer issue more visas until the start of the next fiscal year.

At NEC, we had postdocs who had to delay their start date until October for this reason, including in some cases those who wanted to start at the beginning of summer. With the limit dramatically decreased, if the job market starts perking up, we could hit the limit much earlier. This could make a real dent in international cooperation in science.

One-Way Functions

What is a one-way function, intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal definition has yield two quite different meanings, sometimes causing confusion.

The first directly tries to translate the intuition. A function f is one-way if

1. f is 1-1 (so an inverse is unique),
2. f is length increasing (so the output of the inverse function is not too large),
3. f is computable in polynomial time, and
4. there is no polynomial-time computable g such that for all x, g(f(x))=x.

This is a nice clean definition that fulfills the intuition but is not that useful for cryptography, since f could be easily invertible on all but a small number of inputs, or with stronger adversaries. To handle these issues we have a different looking definition.

A function f is r(n)-secure one-way if

1. There is a function l(n)≥n such that f maps strings of length n to strings of length l(n),
2. f is computable in polynomial time, and
3. for all probabilistic polynomial-time algorithms A, the probability that f(A(f(x)))=f(x) is at most r(n) where the probability is taken over x chosen uniformly from the strings of length n and the random coins used by A.

There are many variations on both definitions and a considerable amount of theory devoted to each. Grollmann and Selman show that one-way functions of the first kind exist if and only if P ≠ UP. On the other hand Håstad, Impagliazzo, Levin and Luby show that from any one-way function of the second kind, one can create a pseudorandom generator.

At one point I tried using complexity-theoretic one-way functions and cryptographic one-way functions to distinguish the two, but this only caused confusion. So we have to live with the fact that we have these two definitions with the same name and we'll have to just use context to figure out which definition is appropriate. If you give a talk or write a paper about one-way functions, it never hurts to distinguish which version you are talking about.

A Speech and A Weblog

UCLA Professor Andrew Kahng gave this wonderful speech to the incoming computer science graduate students. While designed for UCLA, with minor changes it applies to every research institution. Every graduate student or anyone interested in graduate school should read it.

Michael Nielsen, coauthor of my favorite book on quantum computing, has his own weblog. Worth checking out.

Proof, The Movie

We just got email that Proof, a movie adapted from the play, will be filmed in and around the University of Chicago campus over the next few weeks. I saw the play a couple of years ago in New York, a powerful story about an aging mathematician and his daughter. Given the cast, director and source material I would expect great things from the film version as well, and it certainly should best out the last movie I remember them filming here.

Turing, The Novel

Christos Papadimitriou has been exercising his creative talents. He has a new book Turing (A Novel about Computation) building a love story around some of Turing's lectures. He is now working on Logicomix, computer science in comic book form. I can imagine it now, our hero NP-Man and his trusty sidekick P-Girl battle the evil Execution Time.

The Buzz

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima. They claim to show that no polynomial-time machine can produce a proof of a super-polynomial-time lower bound for NP and as a consequence there is no proof that P≠NP in any reasonable proof system such as Peano Arithmetic. The first part I don't really understand but the latter would be a major breakthrough.

But don't get too excited. I have heard from multiple sources that Razborov has found serious problems in their paper, in particular that Theorem 22 is just false. So as one complexity theorist put it, "This is probably not the most important paper on your stack."

Creative Commons

In a conversation I had last week, a professor planned to use slides from lecture notes he found on the web in his own slides. He planned to give attribution to the original producers of the slides but did he need to contact them beforehand for permission. Technically yes, material put on the web is copyrighted by default. But if he sent them email most responses would be of the form, "Please don't waste my time!"

To deal with this issue, Creative Commons has a nice service giving an easy way to release some rights for online material. So I've added a link on the left column of the web log that basically allows you to modify and distribute the material in this weblog for noncommercial use with attribution. No need to ask me, not that anyone has.

On another note, I'm on vacation next week and off the internet. Back after that.

Balanced NP Sets

Last week I posed the following question:

(1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

This question was posed by Ryan O'Donnell and solved by Boaz Barak. Here is a proof sketch.

By using standard padding and encoding tools, (1) is equivalent to

(2) There is an NP-complete language L and a polynomial-time computable function f such that for every n, there are exactly f(n) strings in L of length n.

First we show how to achieve (2) if we replace "strings" with "total witnesses." Consider pair of formulas φ and ¬φ. The total number of satisfying assignments between them total 2ⁿ if the have n variables. We just create an encoding that puts φ and ¬φ at the same length. The total number of witnesses at that length is equal to 2ⁿ times the number of formula pairs encoded at that length.

We now prove (2) by creating a language L that encodes the following at the same length for each φ

1. φ, where φ is satisfiable.
2. (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.

You can check that the language is NP-complete and the total number of strings in L for each φ is just the number of satisfying assignments of φ.

Is P versus NP formally independent?

As promised back in March, the October 2003 BEATCS Complexity Column is on whether we can truly settle the P versus NP question. Scott Aaronson gives quite an interesting survey on this topic.

STOC 2004

I have received some requests for the call for papers for STOC 2004 which will be held in Chicago. Maybe it is because I gave the presentation for STOC 2004 at the 2003 business meeting, or because if you google 'STOC 2004' this weblog comes up in the list, or just because I'm in Chicago now, but I am not officially connected to STOC 2004.

Having said that, here is the tentative call for papers.

Institute of Advanced Study

The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impagliazzo, Manindra Agrawal (with his students Kayal and Saxena at Princeton) and postdocs Boaz Barak, Subhash Khot, Ryan O'Donnell and Nate Segerland. These are just the ones I met yesterday during a short visit several weeks before their semester officially begins. We'll expect great things from them.

Here is a question we thought about yesterday, posed by Ryan O'Donnell and ultimately settled by Boaz Barak:

Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

Think about it. I'll post the proof next week.